动态规划入门深度解析

一句话概括

动态规划（DP）不是新算法，而是一种”把大问题拆成重叠子问题、缓存中间结果”的思维。它的灵魂就三步：定义状态 → 写转移方程 → 填边界。

面试里 DP 占比极高（爬楼梯、背包、编辑距离、最长递增子序列……），难点不在代码，而在”怎么把问题翻译成状态”。本文用几个最小例子把这套翻译过程讲透。

核心知识点

1. 斐波那契：看 DP 的四种进化

同样一个问题，从暴力递归到空间压缩，完整展示 DP 思路的成长：

// ❌ 暴力递归：O(2^n)，fib(50) 直接卡死（大量重复计算）
function fibBad(n) { return n < 2 ? n : fibBad(n - 1) + fibBad(n - 2); }

// ✅ 记忆化（自顶向下）：O(n)，用缓存消重
function fibMemo(n, memo = {}) {
  if (n < 2) return n;
  return memo[n] ??= fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}

// ✅ 自底向上填表：O(n)，最经典的 DP 形式
function fibDP(n) {
  if (n < 2) return n;
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
  return dp[n];
}

// ✅ 滚动变量：dp[i] 只依赖前两个，O(1) 空间
function fib(n) {
  if (n < 2) return n;
  let prev = 0, cur = 1;
  for (let i = 2; i <= n; i++) [prev, cur] = [cur, prev + cur];
  return cur;
}

状态转移：dp[i] = dp[i-1] + dp[i-2]，边界 dp[0]=0, dp[1]=1。

2. 爬楼梯：状态只依赖前 k 个 → 可压缩空间

LeetCode 70：每次爬 1 或 2 阶，到第 n 阶有几种走法？到第 i 阶只能从 i-1 跨一步或 i-2 跨两步，所以 dp[i] = dp[i-1] + dp[i-2]——就是斐波那契换个皮。

function climbStairs(n) {
  if (n < 3) return n;
  let a = 1, b = 2; // dp[1], dp[2]
  for (let i = 3; i <= n; i++) [a, b] = [b, a + b];
  return b;
}
// 若每次可爬 1/2/3 步：dp[i]=dp[i-1]+dp[i-2]+dp[i-3]，滚动三个变量即可

规律：只要状态只依赖前 k 个，就能把 O(n) 空间压成 O(k)。

3. 0/1 背包：二维状态 + 选 / 不选 + 空间压缩

n 件物品，每件重量 w、价值 v、只能取一次，容量 capacity 下求最大价值。

// 状态：dp[i][j] = 前 i 件、容量 j 时的最大价值
// 转移：不选 dp[i-1][j]；选 dp[i-1][j-w]+v；取较大
function knapsack(w, v, capacity) {
  const dp = new Array(capacity + 1).fill(0);
  for (let i = 0; i < w.length; i++) {
    // ❌ 正序会重复选同一件；✅ 逆序保证 dp[j-w] 是上一轮的值
    for (let j = capacity; j >= w[i]; j--)
      dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
  }
  return dp[capacity];
}

完全背包（每件无限次）只需把内层改成正序——因为允许重复选取，dp[j-w] 用本轮已更新的值。这一正一逆是两类背包的分水岭。

4. 编辑距离：二维 DP 代表作

LeetCode 72：把 word1 变成 word2 的最少增 / 删 / 改步数。dp[i][j] = word1 前 i 个字符变 word2 前 j 个字符的最小操作数。

function minDistance(w1, w2) {
  const m = w1.length, n = w2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) dp[i][0] = i; // 删光
  for (let j = 1; j <= n; j++) dp[0][j] = j; // 全插
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = w1[i - 1] === w2[j - 1]
        ? dp[i - 1][j - 1]
        : 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
  return dp[m][n];
}

其实你每天都在用

• 爬楼梯 / 凑零钱：零钱兑换就是完全背包，求”凑成 amount 的最少硬币数”
• 打家劫舍：相邻不能同偷，dp[i]=max(dp[i-1], dp[i-2]+nums[i])，一维 DP
• 最长递增子序列（LIS）：股票、任务排期里”选哪些最优”的底层模型
• 编辑距离：搜索框”你是不是要找 XXX”的拼写纠错就是它
• 最大子数组和：dp[i]=max(nums[i], dp[i-1]+nums[i])，即 Kadane 算法
• React 的 memo / 缓存：本质是”子问题结果缓存”，和记忆化 DP 同思路

常见误解（FAQ）

❌ 误区一：”DP 就是递归 + 缓存，记住模板就行”

模板只是外壳。最难的是状态定义——状态定错了，方程怎么写都别扭。训练方法是刻意练习”把一句话需求翻译成 dp[i] 或 dp[i][j] 代表什么”，这步通了，代码是顺的。

❌ 误区二：”0/1 背包内层循环正序逆序无所谓”

大错。逆序是为了让 dp[j-w] 读的是”上一轮（i-1）”的值，保证每件只选一次；改成顺序，dp[j-w] 就用了本轮已更新的（相当于已选过这件），变成完全背包——结果直接错。

❌ 误区三：”DP 一定比暴力快，所以无脑上 DP”

DP 适合”重叠子问题 + 最优子结构”。如果子问题不重叠（如归并排序的分治），记忆化毫无收益；有些题贪心就能 O(n) 解决，硬上 DP 反而绕远。先看问题性质，再决定武器。

❌ 误区四：”空间压缩随便压，不影响正确性”

压缩要满足”当前状态只依赖有限的旧状态”。二维压一维（背包）可以，因为只依赖上一行；但编辑距离每个格子依赖左、上、左上三个，压成一维容易写错——压缩前先确认依赖关系，别为了省空间把答案压没了。

一句话总结

动态规划不是背题，而是练出”把需求翻译成状态、再把状态串成方程”的肌肉记忆——状态定准、转移写对、边界填好，剩下的只是填表，再复杂的题也会在你手里一层层塌成可解的小块。