动态规划专题导读

很多同学一看到"动态规划"四个字就头皮发麻，其实 DP 没有想象中那么玄学。它本质上就是一种用空间换时间的递推思想：把大问题拆成小问题，把小问题的答案存起来，避免重复计算。这篇导读会帮你建立动规的整体认知，后续文章再逐个模块击破。

一、什么时候该用 DP？

不是所有题目都要上 DP，遇到下面三个信号，基本可以确定往动规方向想：

1. 求最值：问"最多/最少/最长/最大"能是多少，例如最少硬币数、最长子序列。
2. 求方案数：问"有多少种方法/多少条路径"，例如爬楼梯的不同走法。
3. 后面状态依赖前面状态：当前决策会受之前选择的影响，且过程中有重叠子问题（同一个小问题会被反复计算）。

反过来的信号也要记住：如果题目只要求输出具体方案本身（比如把每条路径都列出来），DP 存的只是数量，通常得老老实实回溯；如果每一步局部最优能直接推出全局最优且无需反悔，那是贪心的地盘。

再提两个术语：

• 最优子结构：大问题的最优解可以由小问题的最优解推导出来。这是 DP 能工作的前提。
• 重叠子问题：递归展开后同一个子问题出现多次。这是 DP 比暴力递归快的原因。

二、解题五部曲

做动规题最忌讳上来就写代码。建议固定走五步，每一步都问自己一句话：

五部曲中最容易被轻视的是第 3 步和第 4 步。初始化错一位、遍历方向反了，代码看起来"完全正确"却输出诡异结果——这时候第 5 步打印 dp 数组是最快的排错手段，比盯着代码干瞪眼高效得多。

用 Java 把爬楼梯写完整：

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        // 1. dp[i] 表示爬到第 i 阶的方法数
        int[] dp = new int[n + 1];
        // 3. 初始化递推起点
        dp[1] = 1;
        dp[2] = 2;
        // 4. 从小到大，保证 dp[i-1]、dp[i-2] 已算好
        for (int i = 3; i <= n; i++) {
            // 2. 递推公式
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

三、DP、记忆化递归、贪心怎么选？

这三种思想经常被混为一谈，用一张表说清它们的分工：

三者可以互相转化：把记忆化递归的递归栈展开就是 DP；如果贪心策略恰好能被证明正确（如跳跃游戏），它比 DP 更快。拿不准时优先写 DP，它是三者中最通用、最不容易出反例的。

四、本专题地图

接下来几篇会按下面的顺序推进，每个模块的侧重点不同：

1. 背包问题：01 背包与完全背包的遍历顺序之辨（倒序 vs 正序），以及"组合数 vs 排列数"的双层循环嵌套顺序——背包是半个动规的地基。
2. 打家劫舍与股票：状态机 DP 的两个招牌。打家劫舍从线性走到环形再到树形；股票系列把"持有/不持有"两状态扩展出交易次数、冷冻期等维度。
3. 子序列与编辑距离：单串（LIS）、双串（LCS）、编辑距离的二维 dp 表画法，以及区间 DP 入门（回文子串）。

五、LeetCode 题单总表

按模块分块列出，建议做完一块再进下一块：

入门热身（体会五部曲）

背包问题

打家劫舍与股票

子序列与编辑距离

六、学习建议

• 每题先自己写五部曲的前两步（状态定义 + 递推公式），卡住了再看题解，看完必须合上题解重写一遍。
• 背包部分务必亲手画一维滚动数组的更新表格，倒序遍历不亲手推一遍永远记不牢。
• 股票系列建议把 121 到 309 的状态转移表放在一张纸上对比，状态机的"加维度"套路一眼就通了。
• 二维 DP（LCS、编辑距离、回文）要练到能徒手画出 dp 表并填出前几行。

下一篇我们从背包问题开始，聊聊为什么容量必须倒序遍历这个经典细节。

参考

• 代码随想录 · 动态规划专题