算法篇 ｜ 动态规划

前言

动态规划（Dynamic Programming，简称 DP）是算法面试中最让人头疼的话题之一。很多人觉得 DP 题目”每道都不一样，根本没法总结规律”。但实际上，DP 有一套非常清晰的解题框架。掌握了这套框架，面对大多数 DP 题目你都能找到突破口。

DP 的核心思想可以用一句话概括：把一个大问题拆解成若干个重叠的子问题，通过存储子问题的解来避免重复计算。

它和递归（分治）的区别在于：递归解决的子问题是独立的（比如归并排序），而 DP 解决的子问题是重叠的——同一个子问题会被反复用到。如果不把子问题的结果存起来，就会产生大量重复计算。

本章我们会从 DP 的两大核心概念讲起（最优子结构 + 重叠子问题），然后给出一套通用的解题五步法，最后通过四道经典题目帮你把这套方法论练到位。

诊断自测

Q1：爬楼梯问题——每次可以爬 1 级或 2 级，到达第 n 级台阶有多少种方法？你能写出状态转移方程吗？

Q2：什么是”最优子结构”？什么是”重叠子问题”？它们在 DP 中分别起什么作用？

Q3：自顶向下（记忆化搜索）和自底向上（递推）有什么区别？各有什么优缺点？

一、DP 的核心思想

1.1 最优子结构

如果一个问题的最优解包含了其子问题的最优解，就说这个问题具有最优子结构。

举个例子：从 A 到 C 的最短路径经过 B，那么 A→B 的那段路径一定也是 A 到 B 的最短路径。如果不是，我们换一条更短的 A→B 路径，整体路径就会更短——和”已经是最短”矛盾。

1.2 重叠子问题

斐波那契数列 f(n) = f(n-1) + f(n-2) 是最经典的例子。如果用递归计算 f(5)：

f(5) = f(4) + f(3)
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)

f(3) 被计算了两次，f(2) 被计算了三次。n 越大，重复计算越严重。暴力递归的时间复杂度是 O(2ⁿ)，而用 DP 存储中间结果可以降到 O(n)。

二、解题五步法

拿到一道 DP 题，按下面五步走：

Step 1：定义状态

确定 dp[i]（或 dp[i][j]）表示什么含义。这是最关键也最难的一步。

技巧：通常状态定义和题目问的东西直接对应。题目问”到第 i 个位置的最小花费”，那 dp[i] 就是”到第 i 个位置的最小花费”。

Step 2：写出状态转移方程

dp[i] 如何由之前的状态推导出来？

技巧：想一想”最后一步”做了什么。比如爬楼梯，到达第 i 级的”最后一步”要么是从第 i-1 级上来（1 步），要么是从第 i-2 级上来（2 步）。

Step 3：确定初始条件

最小的子问题的解是什么？比如 dp[0]、dp[1] 等。

Step 4：确定遍历顺序

计算 dp[i] 时，它依赖的状态（如 dp[i-1]、dp[i-2]）必须已经算好了。

Step 5：确定返回值

最终答案是 dp[n]？还是 dp[n-1]？还是 dp 数组中的最大值？

三、经典题目

3.1 爬楼梯（LeetCode 70）

每次可以爬 1 或 2 级台阶，到第 n 级有多少种方法？

五步法：

1. 状态：dp[i] = 到第 i 级台阶的方法数
2. 转移方程：dp[i] = dp[i-1] + dp[i-2]
3. 初始条件：dp[0] = 1, dp[1] = 1
4. 遍历顺序：从小到大
5. 返回值：dp[n]

function climbStairs(n) {
  if (n <= 1) return 1;

  const dp = new Array(n + 1);
  dp[0] = 1;
  dp[1] = 1;

  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
}

空间优化：因为 dp[i] 只依赖 dp[i-1] 和 dp[i-2]，可以用两个变量代替整个数组：

function climbStairs(n) {
  if (n <= 1) return 1;

  let prev2 = 1; // dp[i-2]
  let prev1 = 1; // dp[i-1]

  for (let i = 2; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }

  return prev1;
}

复杂度：时间 O(n)，空间 O(1)。

3.2 零钱兑换（LeetCode 322）

给定不同面额的硬币 coins 和一个总金额 amount，计算凑成总金额所需的最少硬币数。如果无法凑成返回 -1。

五步法：

1. 状态：dp[i] = 凑成金额 i 所需的最少硬币数
2. 转移方程：dp[i] = min(dp[i - coin] + 1) for each coin in coins
3. 初始条件：dp[0] = 0（凑成 0 元需要 0 枚硬币），其余初始化为 Infinity
4. 遍历顺序：从小到大
5. 返回值：dp[amount]，如果仍为 Infinity 则返回 -1

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (i - coin >= 0 && dp[i - coin] !== Infinity) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

理解转移方程：凑金额 i 的”最后一步”是放入一枚面额为 coin 的硬币，那么之前需要凑 i - coin 的金额。在所有可能的”最后一步”中取最小值。

复杂度：时间 O(amount * coins.length)，空间 O(amount)。

3.3 最长递增子序列（LeetCode 300）

给定一个整数数组 nums，找到其中最长严格递增子序列的长度。

注意：这里的”子序列”不要求连续。

五步法：

1. 状态：dp[i] = 以 nums[i] 结尾的最长递增子序列的长度
2. 转移方程：dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]
3. 初始条件：dp[i] = 1（每个元素自身就是长度为 1 的子序列）
4. 遍历顺序：从小到大
5. 返回值：max(dp[0], dp[1], ..., dp[n-1])

function lengthOfLIS(nums) {
  const n = nums.length;
  const dp = new Array(n).fill(1);

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}

注意：返回值不是 dp[n-1]，而是整个 dp 数组的最大值。因为最长递增子序列不一定以最后一个元素结尾。

复杂度：时间 O(n²)，空间 O(n)。

还有一种更优的 O(n log n) 解法，使用贪心 + 二分：

function lengthOfLIS(nums) {
  const tails = []; // tails[i] 表示长度为 i+1 的递增子序列的最小尾部元素

  for (const num of nums) {
    let lo = 0;
    let hi = tails.length;

    // 二分查找第一个 >= num 的位置
    while (lo < hi) {
      const mid = lo + Math.floor((hi - lo) / 2);
      if (tails[mid] < num) {
        lo = mid + 1;
      } else {
        hi = mid;
      }
    }

    tails[lo] = num;
  }

  return tails.length;
}

3.4 0-1 背包问题

有 n 个物品，每个物品有重量 weights[i] 和价值 values[i]。背包容量为 capacity。每个物品只能放一次，求最大价值。

0-1 背包虽然不是 LeetCode 原题，但它是很多 DP 问题的原型，面试中也经常考。

五步法：

1. 状态：dp[i][w] = 前 i 个物品、容量为 w 的背包能装的最大价值
2. 转移方程：
   • 不放第 i 个物品：dp[i][w] = dp[i-1][w]
   • 放第 i 个物品（前提是放得下）：dp[i][w] = dp[i-1][w - weights[i]] + values[i]
   • 取两者的最大值
3. 初始条件：dp[0][w] = 0（没有物品可选）
4. 遍历顺序：外层遍历物品，内层遍历容量
5. 返回值：dp[n][capacity]

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () =>
    new Array(capacity + 1).fill(0)
  );

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      // 不放第 i 个物品
      dp[i][w] = dp[i - 1][w];

      // 放第 i 个物品（如果放得下）
      if (w >= weights[i - 1]) {
        dp[i][w] = Math.max(
          dp[i][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1]
        );
      }
    }
  }

  return dp[n][capacity];
}

空间优化：注意 dp[i][w] 只依赖 dp[i-1][...]，可以压缩成一维数组。但内层循环必须从大到小遍历，防止同一轮中覆盖了还需要用到的值：

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = new Array(capacity + 1).fill(0);

  for (let i = 0; i < n; i++) {
    // 必须从大到小遍历！
    for (let w = capacity; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }

  return dp[capacity];
}

复杂度：时间 O(n * capacity)，空间 O(capacity)。

四、空间优化的通用思路

很多 DP 问题的空间可以从 O(n²) 优化到 O(n)，甚至 O(1)。核心思路是：看 dp[i] 依赖哪些状态。

• 如果只依赖 dp[i-1]：可以用滚动数组（两行交替）或一维数组
• 如果只依赖 dp[i-1] 和 dp[i-2]：可以用两个变量
• 如果依赖当前行的之前列和上一行：需要小心遍历方向

一维数组优化的注意事项：

• 0-1 背包：内层从大到小遍历（确保每个物品只用一次）
• 完全背包：内层从小到大遍历（每个物品可以用多次）

常见误区

误区一：“DP 就是记忆化递归”

记忆化递归是 DP 的一种实现方式（自顶向下），但 DP 的核心是状态定义和转移方程。自底向上的递推也是 DP，而且在很多情况下更优（没有递归栈开销，可以做空间优化）。

误区二：“所有问题都可以用 DP 解决”

DP 要求问题具有最优子结构和重叠子问题。如果子问题之间没有依赖（比如快排的两个子数组），用分治更合适。如果没有最优子结构（比如最长路径问题在一般图上），DP 不适用。

误区三：“状态转移方程是最难的一步”

其实，状态定义比转移方程更关键。状态定义对了，转移方程通常是自然而然的。如果你发现转移方程写不出来，往往是因为状态定义有问题——比如维度不够（需要加一维状态）或者含义不对。

误区四：“空间优化就是把二维数组改成一维”

空间优化不只是”降维”这么简单。你必须确保优化后，计算 dp[i] 时它所依赖的值没有被提前覆盖。这通常需要调整内层循环的遍历方向（比如 0-1 背包必须从大到小遍历）。不理解背后的原因，贸然优化就会出 Bug。

小结

动态规划虽然题目种类多、变体多，但核心方法论是统一的。掌握了解题五步法，面对大多数 DP 题目你都能找到突破口。

核心要点

1. 核心概念：最优子结构 + 重叠子问题
2. 五步法：状态定义 → 转移方程 → 初始条件 → 遍历顺序 → 返回值
3. 想”最后一步”：转移方程的突破口通常是”到达当前状态的最后一步做了什么”
4. 空间优化：根据状态依赖关系，用滚动数组或变量代替完整的 DP 表
5. 两种实现：自顶向下（记忆化递归）和自底向上（递推），各有优劣

本章思维导图

练习挑战

第一题 ⭐：打家劫舍（LeetCode 198）

一个小偷沿街偷窃，每间房屋有一定金额，相邻房屋装有连通报警器。求在不触动报警器的情况下能偷到的最高金额。

// 示例
// 输入: [1, 2, 3, 1]
// 输出: 4（偷第 1 间和第 3 间，1 + 3 = 4）

function rob(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];

  let prev2 = 0; // dp[i-2]
  let prev1 = 0; // dp[i-1]

  for (const num of nums) {
    const curr = Math.max(prev1, prev2 + num);
    prev2 = prev1;
    prev1 = curr;
  }

  return prev1;
}

第二题 ⭐⭐：最长回文子串（LeetCode 5）

给定一个字符串 s，找出其中最长的回文子串。

function longestPalindrome(s) {
  const n = s.length;
  // dp[i][j] 表示 s[i..j] 是否是回文
  const dp = Array.from({ length: n }, () => new Array(n).fill(false));
  let start = 0;
  let maxLen = 1;

  // 单个字符都是回文
  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
  }

  // 按长度从小到大遍历
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;

      if (s[i] === s[j]) {
        if (len === 2 || dp[i + 1][j - 1]) {
          dp[i][j] = true;
          if (len > maxLen) {
            start = i;
            maxLen = len;
          }
        }
      }
    }
  }

  return s.substring(start, start + maxLen);
}

function longestPalindrome(s) {
  let start = 0;
  let maxLen = 1;

  function expand(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      if (right - left + 1 > maxLen) {
        start = left;
        maxLen = right - left + 1;
      }
      left--;
      right++;
    }
  }

  for (let i = 0; i < s.length; i++) {
    expand(i, i);     // 奇数长度回文
    expand(i, i + 1); // 偶数长度回文
  }

  return s.substring(start, start + maxLen);
}

第三题 ⭐⭐⭐：编辑距离（LeetCode 72）

给定两个字符串 word1 和 word2，计算将 word1 转换成 word2 所使用的最少操作数。可以执行三种操作：插入、删除、替换。

function minDistance(word1, word2) {
  const m = word1.length;
  const n = word2.length;

  // dp[i][j] = word1 前 i 个字符变成 word2 前 j 个字符的最少操作数
  const dp = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(0)
  );

  // 初始条件
  for (let i = 0; i <= m; i++) dp[i][0] = i; // 删除 i 个字符
  for (let j = 0; j <= n; j++) dp[0][j] = j; // 插入 j 个字符

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]; // 字符相同，不需要操作
      } else {
        dp[i][j] = Math.min(
          dp[i - 1][j] + 1,     // 删除
          dp[i][j - 1] + 1,     // 插入
          dp[i - 1][j - 1] + 1  // 替换
        );
      }
    }
  }

  return dp[m][n];
}

自我检测

• 能解释最优子结构和重叠子问题的含义
• 能熟练运用解题五步法（状态→转移→初始→遍历→返回）
• 能解决爬楼梯问题，并做空间优化到 O(1)
• 能写出零钱兑换的状态转移方程，并解释”想最后一步”的思路
• 能区分 0-1 背包和完全背包的空间优化中遍历方向的不同
• 能用 DP 或中心扩展法解决最长回文子串
• 能说出自顶向下和自底向上两种实现的优缺点
• 遇到新的 DP 题时，能快速定义状态并尝试写出转移方程