动态规划怎么入门？爬楼梯和最长递增子序列怎样做？

简答

爬楼梯：每次能上 1 级或 2 级，上到第 n 级有几种走法？到第 n 级的最后一步，要么从第 n-1 级跨 1 级上来，要么从第 n-2 级跨 2 级上来，所以走法数等于这两者之和。大问题的答案由更小问题的答案组成，这就是动态规划能用的前提。

直接写递归 f(n) = f(n-1) + f(n-2) 会很慢，因为 f(n-2) 在算 f(n-1) 时又会被算一遍，越往下重复越多，是指数级。动态规划的做法是把算过的结果存起来，从小到大依次算，每个只算一次，变成 O(n)。

解题分三步：先定义状态，dp[i] 代表什么；再找转移方程，dp[i] 怎样由前面的值算出来；最后定初始值，最小的几个答案是多少。想清楚 dp[i] 的含义是最关键的一步。

最长递增子序列是个更典型的例子：dp[i] 表示以第 i 个数结尾的最长递增子序列长度，它等于前面所有比它小的数的 dp 最大值加 1，整体 O(n²)。要注意，答案是所有 dp[i] 的最大值，不是 dp 的最后一项。Vue 3 的 diff 用到了这个算法的 O(n log n) 版本。

爬楼梯

function climbStairs(n) {
  if (n <= 2) return n;
  let prev = 1; // dp[i-2]
  let current = 2; // dp[i-1]
  for (let i = 3; i <= n; i++) {
    [prev, current] = [current, prev + current];
  }
  return current;
}

function lengthOfLIS(nums) {
  const dp = new Array(nums.length).fill(1);
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
  return nums.length === 0 ? 0 : Math.max(...dp);
}

function lengthOfLISFast(nums) {
  const tails = [];
  for (const num of nums) {
    let left = 0;
    let right = tails.length;
    while (left < right) {
      const mid = (left + right) >> 1;
      if (tails[mid] < num) left = mid + 1;
      else right = mid;
    }
    tails[left] = num;
  }
  return tails.length;
}

console.log(climbStairs(5)); // 8
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4
console.log(lengthOfLISFast([10, 9, 2, 5, 3, 7, 101, 18])); // 4
console.log(lengthOfLIS([])); // 0

climbStairs 为什么只用两个变量，没有开数组？因为 dp[i] 只依赖前两项，更早的值算完就用不到了。只保留需要的两项，空间从 O(n) 降到 O(1)，这是动态规划常见的空间优化。

lengthOfLIS 里，以 7 结尾的最长递增子序列，是在前面比 7 小的 2、5、3 里找 dp 最大的，5 和 3 的 dp 都是 2，所以 dp 为 3，比如 2, 3, 7。最后的 101 和 18 都能接在 7 后面，长度是 4。

lengthOfLISFast 换了思路：tails[k] 记录长度为 k+1 的递增子序列中，结尾最小的那个数。结尾越小，后面越容易接上新数。每来一个数，用二分查找它在 tails 里的位置，替换或追加。tails 的长度就是答案，但要注意它本身不一定是一个真实的子序列。

怎样判断能不能用动态规划

题目问“最多”“最少”“有几种”，而且大问题可以由规模更小的同类问题推出来，就可以考虑动态规划。比如零钱兑换问最少几枚硬币、编辑距离问最少改几次、背包问题问最大价值。

如果每一步的选择只需看眼前、不会影响以后，比如找零时硬币面额是 1、5、10 这样的倍数关系，贪心就够了；面额不规则时贪心会出错，比如面额是 1、3、4，凑 6 时贪心先拿 4，再拿两个 1，一共 3 枚，而最优是两个 3，这时就得用动态规划。

常见追问

记忆化递归和动态规划有什么区别？

本质一样，都是把子问题的答案存起来。记忆化递归从大问题往下拆，用到哪个子问题才算哪个，写法接近原始思路；动态规划从小问题往上推，用循环填表，没有递归栈溢出的风险。

Vue 3 为什么要用最长递增子序列？

列表中间乱序的部分，把新节点在旧列表里的位置排出来，最长递增子序列里的节点相对顺序没变，可以不动，只移动其他节点，移动次数最少。见《Vue 2 的 diff 算法是怎样比较子节点的？》。