动态规划入门：记住算过的结果

这一课你将能做到

1. 说出动态规划两要素（最优子结构、重叠子问题）和解题四步（定义、转移、初值、遍历）
2. 用滚动变量写爬楼梯，用 0/1 背包模型解决分割等和子集
3. 写出最长递增子序列的 DP 解法，并推导出编辑距离的二维状态转移

为什么要学

动态规划（DP）是很多人心里的「终极大 BOSS」：听题解时醍醐灌顶，自己写无从下手。其实它只比递归多一个朴素动作——把算过的子问题结果存起来，下次直接取用。回溯之所以指数爆炸，是因为相同的子问题被算了成千上万遍；DP 用一张表消掉这些重复，常常把 O(2ⁿ) 直接压到 O(n²)。

DP 在工程里离你并不远：路径规划、文本比对（Git diff 就是编辑距离的变体）、资源分配、推荐系统的序列建模都有它的影子。作为收官课，本课用四道由浅入深的经典题帮你建立通用解题框架。能拿下这四题，LeetCode 中等难度的 DP 题你就具备了「读题拆状态」的基本能力。

先建立图像

先看递归的浪费与 DP 的节省（以爬楼梯为例，到第 n 阶）：

递归树：f(5)
        /        \
     f(4)        f(3)      ← f(3) 在整棵树里被反复计算
     /  \        /  \
  f(3) f(2)   f(2) f(1)
   ...大量重复...

DP：f(1)=1, f(2)=2 → f(3)=3 → f(4)=5 → f(5)=8
    每个子问题只算一次

解题四步法（每道 DP 题都按这个顺序想）：

1. 定义状态：dp[i]（或 dp[i][j]）到底表示什么？
2. 写转移方程：当前状态从哪些更早的状态来？
3. 定初始值与边界：最小的状态是多少？
4. 确定遍历顺序：保证算当前值时，依赖的值已经算好。

跟着做

步骤 1：LeetCode 70「爬楼梯」（简单）

每次可爬 1 或 2 阶，到第 n 阶共多少种走法。

定义 dp[i] = 到第 i 阶的走法数。到达第 i 阶的最后一步，要么从 i-1 跨 1 阶、要么从 i-2 跨 2 阶，两类互斥：dp[i] = dp[i-1] + dp[i-2]。

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int prev2 = 1; // dp[1]
        int prev1 = 2; // dp[2]
        for (int i = 3; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

逐点讲：每次只依赖前两个值，用两个滚动变量即可，不必开数组。时间 O(n)，空间 O(1)。这题就是斐波那契模型，也是理解 DP 的第一块台阶。

步骤 2：LeetCode 416「分割等和子集」（中等，0/1 背包）

判断能否把数组分成两个和相等的子集。

转化：总和为 sum，问题等价于「能否选出若干数，恰好凑成 sum/2」——这正是 0/1 背包（每个数选或不选，只能用一次）。

定义 dp[j] = 能否（true/false）凑出和 j。对每个数 num，从目标容量倒序更新（倒序保证每个数只用一次）：

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int x : nums) sum += x;
        if (sum % 2 != 0) {
            return false; // 和为奇数，无法平分
        }
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true; // 什么都不选，凑出 0
        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num]; // 不选 / 选 num
            }
        }
        return dp[target];
    }
}

逐点讲：必须倒序遍历 j。若正序，同一个 num 可能在一轮里被重复使用（等价于完全背包）。时间 O(n·target)，空间 O(target)。理解这题，就掌握了背包问题「选 / 不选」的统一更新法。

步骤 3：LeetCode 300「最长递增子序列」（中等）

求数组中最长严格递增子序列长度（子序列不要求连续）。

定义 dp[i] = 以 nums[i] 结尾的最长递增子序列长度。对每个 i，回头看所有 j < i，若 nums[j] < nums[i]，就可以接在后面：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int best = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1; // 只选自己
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            best = Math.max(best, dp[i]);
        }
        return best;
    }
}

逐点讲：答案不一定以最后一个元素结尾，所以要用 best 跟踪全局最大，不能直接返回 dp[n-1]。时间 O(n²)，空间 O(n)。

进阶：贪心 + 二分可优化到 O(n log n)——维护数组 tails，tails[k] 表示长度 k+1 的递增子序列的最小可能尾值，每来一个数用二分找它的归位。面试先给 O(n²) DP，再口述优化即可。

步骤 4：LeetCode 72「编辑距离」（困难，二维 DP）

把 word1 变成 word2，允许插入、删除、替换，求最少操作数。

二维状态：dp[i][j] = word1 前 i 个字符变成 word2 前 j 个字符的最少操作。两字符相等时无需操作，直接沿用 dp[i-1][j-1]；不等时取三种操作的最小值加 1：

• 删除 word1 的字符：来自 dp[i-1][j]
• 插入一个字符：来自 dp[i][j-1]
• 替换：来自 dp[i-1][j-1]

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = i; // 全删除
        for (int j = 0; j <= n; j++) dp[0][j] = j; // 全插入
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j],
                                   Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
                }
            }
        }
        return dp[m][n];
    }
}

逐点讲：注意 dp 下标比字符下标多 1，首行首列是边界初值。时间 O(m·n)，空间 O(m·n)（可用滚动行优化到 O(n)）。这题是二维 DP 的范本：状态、转移、初值三件事齐全，能独立推出，DP 就算真正入门。

讲清楚要点

1. 先判断是不是 DP 题：信号是「重叠子问题 + 求最优（最大/最小/能否/方案数）」，递归写法出现重复参数时尤其明显。
2. 状态定义是成败关键：dp[i] 往往带「以 i 结尾 / 前 i 个」的限定，定义错了转移必然拧巴。
3. 背包就分倒序与正序：每种物品只能用一次 → 倒序（0/1 背包）；可用无限次 → 正序（完全背包，LeetCode 322 零钱兑换）。
4. 二维 DP 先画表格再写代码：在纸上填 2×2 的格子，确认 dp[i][j] 从哪三个方向来，比空想可靠。
5. 答案位置要核对：有全局限定的题（LIS）取过程最大值；有明确终点的题（编辑距离）取右下角。

你可能会懵的地方

• DP 和记忆化搜索（递归 + 备忘录）什么区别？ 数学等价，只是求解方向不同：记忆化是自顶向下（从大问题问到小问题），DP 是自底向上（先算小问题再拼大问题）。新手先写记忆化往往更自然，再翻译成迭代 DP。

• 背包为什么倒序就能防止重复使用？ 倒序更新时，dp[j-num] 还是「本轮 num 没有参与过」的旧状态；正序时 j-num 更小、在本轮已被更新过，等于允许 num 被反复选取。

• 编辑距离的「插入」为什么来自 dp[i][j-1]？ 在 word1 前 i 个字符基础上插入一个等于 word2 第 j 位的字符即可匹配，所以前提是「前 i 个已匹配前 j-1 个」，操作 +1。

• 状态压缩（二维降一维）什么时候能做？ 当第 i 行只依赖第 i-1 行时可用滚动数组；编辑距离依赖左上、上、左三格，用一维数组时要额外保存「左上」旧值。

• DP 题解看得懂但自己想不到状态怎么办？ 正常。前 20 道 DP 是「学状态」阶段：先背熟本题四题的状态定义，做新题时对照套用（序列类想 i 结尾、双串类想 i,j 前缀、背包类想容量），模式会逐步迁移。

错法对照

错法	问题	正解
背包容量正序遍历	同一物品被重复选取	0/1 背包倒序更新
LIS 直接返回 dp[n-1]	最长序列可能在中间结束	维护全局 best
编辑距离字符相等也 +1	相等本应零成本沿用	直接取 dp[i-1][j-1]
爬楼梯开数组不滚动	结果对但浪费空间	两变量滚动 O(1)
忘记初始化首行首列	第一行/列转移来源为默认 0，错误	显式设置边界

卡点急救

1. 转移方程写不出：回到最笨的办法，写出暴力递归的数学表达式，再问「这个递归的参数是什么、有哪些重复」，参数即状态、表达式即转移。
2. 样例答案总差一：先检查状态定义中 i 的含义（前 i 个还是第 i 个），字符比对时记得 charAt(i-1)；再检查初值。
3. 背包题结果异常大：几乎可以肯定用了正序，把物品多次计入；改成从大到小遍历容量。

面试常问

• 零钱兑换（LeetCode 322）怎么做？属于哪类背包？ 完全背包：dp[j] 表示凑金额 j 的最少硬币数，转移 dp[j] = min(dp[j], dp[j-coin]+1)，容量正序遍历（硬币可重复用），初值 dp[0]=0、其余无穷大。与 416 的区别只在「物品次数」和「求最值而非能否」。

• 编辑距离有什么实际应用？ 拼写纠错、Git 的 diff 与文件比对、DNA 序列对齐、语音识别的候选打分。工程实现会在二维 DP 上做空间压缩与回溯路径（输出具体编辑步骤）。

• 一维 DP 能不能再降复杂度？以 LIS 为例。 能。贪心维持「各长度的最小尾值」+ 二分插入，O(n log n)。这是「DP + 数据结构加速」的经典组合，面试官常用它区分「会背模板」和「理解单调性」。

自测三问

1. 动态规划的解题四步是什么？状态定义里常见的两种限定语是什么？
2. 0/1 背包与完全背包在遍历顺序上的差别及其原因？
3. 编辑距离 dp[i][j] 在字符相等 / 不等时分别怎么取？三个方向各代表什么操作？

小结一句话

动态规划就是「拆状态、记结果」：定义带限定、转移找前驱、初值先铺好，背包记倒序、双串画表格，重叠子问题一处只算一次。

延伸

• 巩固练习：LeetCode 322 零钱兑换、LeetCode 1143 最长公共子序列、LeetCode 198 打家劫舍
• 在本站在线判题平台提交四道主课题目，对照平台返回值检查边界（n=1、空串、无法平分）
• 课程收官：回到 LeetCode 路线图复盘全部 12 课，按 intro 课的计划安排二刷与模拟周测；刷得动、讲得清、能迁移，就是最好的结业状态