DP 刷题指南

学习路径

按照这个顺序刷题，逐步掌握 DP。

---

第一阶段：入门 ⭐

目标

掌握一维 DP 的核心思想，理解「最优子结构」和「重叠子问题」。

必刷题

1. 70 - 爬楼梯
2. 509 - 斐波那契数
3. 198 - 打家劫舍
4. 413 - 等差数列划分
5. 746 - 使用最小花费爬楼梯

核心模板

// 一维 DP 标准模板
function oneDimensionDP(nums: number[]): number {
  // dp[i] = 以 i 结尾的最优解
  const dp = Array(nums.length).fill(0);

  // 初始条件
  dp[0] = nums[0];
  if (nums.length > 1) dp[1] = ...;

  // 状态转移
  for (let i = 2; i < nums.length; i++) {
    dp[i] = Math.max/min(dp[i-1], dp[i-2] + nums[i]);
  }

  return dp[n-1];
}

// 空间优化版
function optimizedDP(nums: number[]): number {
  let prev2 = 0, prev1 = nums[0];

  for (let i = 1; i < nums.length; i++) {
    const curr = Math.max/min(prev1, prev2 + nums[i]);
    prev2 = prev1;
    prev1 = curr;
  }

  return prev1;
}

---

第二阶段：序列DP ⭐⭐

目标

掌握二维 DP，理解「两个字符串/数组」的关系。

必刷题

1. 300 - 最长递增子序列 (LIS)
2. 1143 - 最长公共子序列 (LCS)
3. 72 - 编辑距离
4. 516 - 最长回文子序列
5. 5 - 最长回文子串

核心模板

// 二维 DP 标准模板 - LCS/LIS
function twoDimensionDP(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    Array(n + 1).fill(0)
  );

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i-1] === s2[j-1]) {
        dp[i][j] = dp[i-1][j-1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
      }
    }
  }

  return dp[m][n];
}

---

第三阶段：背包DP ⭐⭐

目标

掌握「选择/不选择」的建模方式。

必刷题

1. 416 - 分割等和子集
2. 494 - 目标和
3. 474 - 一和零
4. 518 - 零钱兑换 II
5. 322 - 零钱兑换

核心模板

// 0/1 背包
function knapsack01(weights: number[], values: number[], W: number): number {
  const dp = Array(W + 1).fill(0);

  for (let i = 0; i < weights.length; i++) {
    // 倒序遍历！
    for (let j = W; j >= weights[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    }
  }

  return dp[W];
}

// 完全背包
function completeKnapsack(weights: number[], values: number[], W: number): number {
  const dp = Array(W + 1).fill(0);

  for (let i = 0; i < weights.length; i++) {
    // 正序遍历！
    for (let j = weights[i]; j <= W; j++) {
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    }
  }

  return dp[W];
}

---

第四阶段：路径DP ⭐⭐

目标

掌握网格/棋盘类问题的状态转移。

必刷题

1. 62 - 不同路径
2. 63 - 不同路径 II
3. 64 - 最小路径和
4. 120 - 三角形最小路径和
5. 174 - 地下城游戏

---

第五阶段：股票DP ⭐⭐

目标

掌握「状态机」建模，理解多个状态的转移。

核心状态

dp[i][0] = 第 i 天不持有股票
dp[i][1] = 第 i 天持有股票
dp[i][2] = 第 i 天处于冷冻期（可选）

模板

function stockDP(prices: number[]): number {
  let dp0 = 0;           // 不持有
  let dp1 = -Infinity;  // 持有

  for (const price of prices) {
    const newDp0 = Math.max(dp0, dp1 + price);
    const newDp1 = Math.max(dp1, dp0 - price);
    dp0 = newDp0;
    dp1 = newDp1;
  }

  return dp0;
}

---

第六阶段：进阶 ⭐⭐⭐

目标

掌握区间DP、树形DP、状态压缩DP。

必刷题

区间DP:
1. 312 - 戳气球
2. 486 - 预测赢家

树形DP:
1. 124 - 二叉树最大路径和
2. 337 - 打家劫舍 III

状态压缩:
1. 698 - 划分为k个相等的子集
2. 526 - 优美的排列

---

做题四步法

[!abstract] 每道题都这样分析

1. 暴力递归是什么？
   - 最后一步是什么？
   - 如何分解为子问题？

2. 加备忘录（记忆化）
   - 哪些状态会重复计算？
   - 用什么作为 dp 的维度？

3. 写成 DP 表
   - dp[i][j] 的含义是什么？
   - 转移方程怎么写？
   - 初始条件？

4. 空间优化
   - 哪些维度可以压缩？
   - 滚动数组怎么写？

---

常见错误

错误	正确做法
0/1 背包正序遍历	倒序遍历
LIS 用 O(n²) 没优化	二分优化到 O(n log n)
股票状态转移写错	画状态转移图
边界条件没考虑	检查 i=0, j=0 的情况
空间优化后数据被覆盖	用临时变量保存

---

参见: **DP算法索引** | **面试真题分类**