动态规划入门 - 算法与数据结构教程

讲解

动态规划（DP）是「递归 + 记忆化」的自底向上形态：问题可拆成重叠的子问题，且最优解可由子问题的最优解组合出来（最优子结构）。与其说它是一种算法，不如说是一套思维流程，五步固定动作：一、定义状态（dp[i] 到底表示什么，语义越精确越好）；二、写状态转移方程（dp[i] 由哪些前面的状态推出）；三、定初始值（最小子问题的答案）；四、确定遍历顺序（保证转移依赖的状态已经算好）；五、从 dp 表读出答案。五步里状态定义是灵魂，定义歪了后面全歪。

用爬楼梯建立直觉：f(n) = f(n-1) + f(n-2)，因为最后一步要么跨 1 级要么跨 2 级——转移方程不是背出来的，是从「最后一步 / 最后一次决策」推出来的。这个「枚举最后一次选择」的思考方式几乎适用于所有入门 DP：打家劫舍的最后一家「偷或不偷」、LIS 的「以谁结尾」。

打家劫舍教会我们状态设计的进阶技巧：单变量 dp[i] 不够用时就升维——prevYes/prevNo 分别记录「偷到第 i 家时偷 / 不偷第 i 家」的最大收益。最长递增子序列（LIS）则展示同一问题的两个层级：朴素 DP 是 O(n²)（dp[i] = 以 nums[i] 结尾的最长递增长度，向前找所有更小的 j）；贪心 + 二分的 tails 数组法做到 O(n log n)——tails[k] 表示「长度为 k+1 的递增子序列的最小结尾值」，维护它单调递增，每个元素二分插入。后者不好想但极漂亮，值得背。

空间优化是 DP 的家常便饭：转移只依赖前几个状态时，滚动变量代替整个数组（爬楼梯只用两个变量），空间从 O(n) 降到 O(1)。

示例

爬楼梯（滚动变量）、打家劫舍（双状态）、LIS（tails + 二分，O(n log n) 版）：

import assert from 'node:assert/strict';

function climbStairs(n) {
  let a = 1; // f(0)：地面算 1 种
  let b = 1; // f(1)
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b]; // f(n) = f(n-1) + f(n-2)
  }
  return b;
}

function rob(nums) {
  let prevNo = 0; // 到前一家为止、不偷前一家的最大收益
  let prevYes = 0; // 偷前一家的最大收益
  for (const x of nums) {
    const curYes = prevNo + x; // 偷这家：上一家必须没偷
    const curNo = Math.max(prevNo, prevYes); // 不偷这家：上一家随意
    prevNo = curNo;
    prevYes = curYes;
  }
  return Math.max(prevNo, prevYes);
}

// LIS：tails[k] = 长度 k+1 的递增子序列的最小结尾，二分维护
function lengthOfLIS(nums) {
  const tails = [];
  for (const x of nums) {
    let lo = 0;
    let hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = x; // 替换或追加：让同长度的结尾尽量小
  }
  return tails.length;
}

assert.strictEqual(climbStairs(2), 2);
assert.strictEqual(climbStairs(3), 3);
assert.strictEqual(climbStairs(10), 89);

assert.strictEqual(rob([1, 2, 3, 1]), 4);
assert.strictEqual(rob([2, 7, 9, 3, 1]), 12);
assert.strictEqual(rob([5]), 5);

assert.strictEqual(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]), 4); // [2,3,7,101] 等
assert.strictEqual(lengthOfLIS([7, 7, 7]), 1); // 严格递增

console.log('DP 入门示例全部通过');

LIS 的 tails 数组不直接等于某个真实子序列，但它的长度就是答案——理解「为什么维护最小结尾能让后续元素更容易接上」是关键：结尾越小，未来可接的元素越多，这是贪心选择。二分查找第一个 >= x 的位置替换之，正是第四章 lower_bound 的复用。

常见坑

状态定义含糊：「dp[i] 表示前 i 个」和「dp[i] 表示以第 i 个结尾」是两种不同定义，转移方程完全不同——先写清语义再写方程。
初始值拍脑袋：初始值是「最小子问题的真实答案」，爬楼梯 f(0)=1 是人为约定（配合递推），打家劫舍全零是真实含义，逐个想别套模板。
遍历顺序错误：转移依赖谁就先算谁；二维 DP 里行序列序反了会用到还没算的格子。
过度空间优化：滚动变量省空间但可读性差，先写清晰的全数组版调通，再优化。
所有计数/最值题都硬套 DP：有重叠子问题 + 最优子结构才适用；贪心能解的题用 DP 是杀鸡用牛刀（两章后对比）。

小结

DP 五步法：定义状态、转移方程、初始值、遍历顺序、读答案；从「最后一次选择」推转移；状态不够就升维，空间富余可滚动。下一章是 DP 的经典战役：背包问题。