Lstmxx的空间

动态规划

解题框架

明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。

自顶向下

通过递归树而从上向下延伸的解题方式，一般用递归来解题。

框架

function coinChange(coins: List[int], amount: int) {
  // 备忘录
  const dpTable = {};
  function dp(n) {
    // 查备忘录，避免重复计算
    if (dpTable[n]) return dpTable[n];
    if (n === 0) return 0;
    if (n < 0) return -1;
    let res = Number.POSITIVE_INFINITY;
    const coinsLen = coins.length;
    for (let i = 0; i < coinsLen; i++) {
      const num = dp(n - coins[i]);
      if (num === -1) continue;
      res = Math.min(res, 1 + num);
    }
    // 记入备忘录
    dpTable[n] = res === Number.POSITIVE_INFINITY ? -1 : res;
    return dpTable[n];
  }

  return dp(amount);
}

自底向上

从递归树最底下往上推出来的解题方式，一般用循环迭代来解题。

function jump(nums: number[]): number {
  // dp 数组
  const dp: number[] = Array.from(Array(nums.length), () => {
    return nums.length + 1;
  });
  // 一般第一个状态都是0
  dp[0] = 0;
  // 遍历dp数组
  for (let i = 0; i < dp.length; i++) {
    for (let j = 1; j <= nums[i]; j++) {
      if (i + j >= nums.length) return dp[dp.length - 1];
      dp[i + j] = Math.min(dp[i + j], 1 + dp[i]);
    }
  }
  // 最后一个便是我们的目标状态了
  return dp[dp.length - 1];
}