动态规划与贪心

动态规划是面试翻车的重灾区——不是因为思想有多难,而是因为候选人还没说清 dp[i] 是什么意思,手就先伸向了 dp[] 数组。这节课把 DP 拆回它真正的地基:它不过是数学归纳法——一个 base case,加一条把小答案长成大答案的规则。我们会拿一道题走完从暴力递归到一行自底向上表格的完整阶梯(LC 120 Triangle),然后横扫整个家族——序列 DP、双序列网格 DP、字符串 DP——最后停在 DP 悄悄输给贪心的地方:Jump Game 和切绳子。

DP 的心法:带备忘录的归纳法

这节课最有用的一次重新表述:动态规划就是会记账的数学归纳法。归纳需要两样东西——一个 base case,和一条从前面若干步推出第 n 步的规则。DP 在此之上只加了一件事:把每个答案写进表里,于是重叠子问题只算一次,而不是指数级重算。所谓「用空间换时间的存储」,全部戏法就在这一句。

把它变成一张你对每道题都跑一遍的清单:

1. 定义——精确说清 dp[i] 或 dp[i][j] 是什么。难度的 80% 在这里,剩下的都是记账。
2. Base case / start——能直接填出来的最小状态。
3. 转移 / 归纳规则——当前状态如何依赖之前的状态。它是往回看一步、几步,还是全部前面的状态?这个问题决定了内层循环的样子。
4. 终止 / 答案——哪个格子(或对哪些格子取 max/min)是最终答案。
5. 优化——依赖模式看清后,压缩空间。

DP 和递归是同一条递推式的两个方向,而面试官很爱听你把这个区别讲出来:

什么样的题面本身就在提示 DP?留意这些关键词信号:max/min、longest/shortest、count 有多少种方案,或对一个序列的 yes/no / true-false 可行性判断。笔记里强调了一条老实的注意事项:DP 给你的是最优值,不是达成它的具体方案。如果题目要的是真正的分配——具体怎么切、具体是哪个句子——你要么回溯已填好的表,要么退回 DFS。记住这一点,它决定了后面的 Word Break II。

Fibonacci:一条递推式,三副身体

Fibonacci(以及它的孪生兄弟 Climbing Stairs——ways(n) = ways(n-1) + ways(n-2))是最小的 DP,也是「优化步」最干净的演示。递推式是死的:f(n) = f(n-1) + f(n-2),base case f(0)=0, f(1)=1。变的只有实现。

朴素递归是两行函数,也是性能陷阱:f(5) 会把 f(3) 算两遍、f(2) 算三遍,调用树膨胀到 O(2ⁿ)。O(n) 表格解决了这个问题——从左到右填 dp[0..n]。但看转移:dp[i] 只读 dp[i-1] 和 dp[i-2]。两个变量就够了,于是我们降维到 O(1) 空间:

public long fib(int n) {
    if (n < 0) throw new IllegalArgumentException();
    if (n <= 1) return n;                // base case f(0)=0, f(1)=1
    long pp = 0, p = 1, ans = 1;    // 覆盖前两项的滑动窗口
    for (int i = 2; i <= n; i++) {
        ans = p + pp;                     // f(i) = f(i-1) + f(i-2)
        pp = p;                           // 窗口整体前移一格
        p = ans;
    }
    return ans;
}

这个教训能推广到 Fibonacci 之外:DP 优化几乎从不改善时间——它靠塌缩维度把空间买回来。找出转移碰到哪些前面的格子,只留这些,把表的其余部分扔掉。

递归 → 记忆化 → DP 阶梯(LC 120 Triangle)

如果这节课你只吃透一道题,就选 LC 120 Triangle:给一个数字三角形,求从顶到底的最小路径和,每步只能走到下一行相邻的数。它是「暴力递归如何变成一行 DP」最清楚的演示。

先热身「怎么建每一行」。LC 118 Pascal's Triangle 是纯归纳——每个内部元素是 pre.get(j-1) + pre.get(j),两边是 1。LC 119 Pascal's Triangle II 要求 O(k) 空间只返回某一行;技巧是从右往左原地更新同一个 list,让每个格子在它左邻居已经贡献之后才被覆盖。正是这个思路让 Triangle 的表能压到一维。

现在按「顿悟程度」排列 Triangle 的四种解法:

• S1 — 遍历所有路径的 DFS。从 (i, j) 递归进 (i+1, j) 和 (i+1, j+1),带着 running sum,在底行更新全局 min。正确,但两个分支重叠:三角形深处的一个节点会被多条路径到达,所以代价是 1 + 2 + 2² + … = O(2ⁿ),不是 O(n²)。
• S2 — divide & conquer 递归。返回 min(left, right) + triangle[i][j],而不是把 sum 顺着参数往下传。更干净,仍是 O(2ⁿ)——同样的重叠子问题。
• S3 — 记忆化递归(剪枝)。加一个初始化为 -1 的 dp[i][j] 缓存并短路:if (dp[i][j] != -1) return dp[i][j];。就这一行,把指数树塌成 O(n²)——每个节点只算一次。这就是自顶向下 DP。
• S4 — 自底向上 DP。从最后一行开始(每个节点的最小路径就是它自己),向上滚。因为你总是先算孩子再算父亲,永远不需要剪枝检查——依赖顺序保证了新鲜。

而且自底向上能漂亮地压成一维数组,因为第 k 行只需要第 k+1 行:

public int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();
    int[] dp = new int[n + 1];         // 多留一格,让底行的 dp[j+1] 不越界
    for (int i = n - 1; i >= 0; i--) {   // 从底部往上建
        for (int j = 0; j <= i; j++) {    // 第 i 行有 i+1 个元素
            dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
        }
    }
    return dp[0];
}

序列 DP:最长连续段

第一个真正的家族是序列 DP,这里 dp[i] 概括了以下标 i 结尾的前缀的某个性质。最干净的例子:无序数组里最长上升连续段的长度。这里 substring 是连续、subsequence 是保序但可跳——面试官故意把这个区别模糊掉。

连续版里,dp[i] = 以 i 结尾的最长上升段长度:若 arr[i] > arr[i-1] 则 dp[i] = dp[i-1] + 1,否则重置为 1;答案是 running max。因为 dp[i] 只读 dp[i-1],一个变量就能替掉数组——O(1) 空间。

子序列版就是大名鼎鼎的 LC 300 Longest Increasing Subsequence,它值得一个专门的技巧。O(n²) 的 DP(dp[i] = 以 i 结尾的最长 LIS,扫所有 j < i)当然可以,但优雅的 O(n log n) 解法维护一个 tails 数组——tails[k] 是所有长度为 k+1 的上升子序列里最小的那个结尾——并对每个新元素二分它的插入位置。被搜索的数组是算法自己建出来、且构造上始终有序的,这个套路我们在 二分作为子过程那节第一次见过。

序列 DP:Kadane 一家

三道紧挨着的经典,一旦定义拿捏准了,都能活在 O(1) 滚动状态里。

LC 53 Maximum Subarray 是原型(Kadane 算法)。定义 dp[i] = 以 i 结尾的最大子数组和。选择是二元的:延续前面的段,还是从头开始——dp[i] = nums[i] + max(dp[i-1], 0)。答案是 max(dp[i])。那个 max(dp[i-1], 0) 就是全部思想:负的前缀比什么都不带还糟,直接丢掉。

LC 152 Maximum Product Subarray 长得一模一样,却是个漂亮的陷阱。乘法让符号变得要紧:一个很大的负积,一遇到另一个负数,瞬间变成最好的积。所以你必须同时带上 running max 和 running min:

public int maxProduct(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int maxPre = nums[0], minPre = nums[0], globalMax = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int a = maxPre * nums[i], b = minPre * nums[i];
        int max = Math.max(nums[i], Math.max(a, b));   // 以此结尾的最优
        int min = Math.min(nums[i], Math.min(a, b));   // 以此结尾的最差——将来一个负数可能翻转它
        globalMax = Math.max(globalMax, max);
        maxPre = max;                                // 两个极值一起往前带
        minPre = min;
    }
    return globalMax;
}

LC 198 House Robber 是同一副滚动形状披了个故事:不能抢相邻两家,于是 dp[i] = max(dp[i-1], dp[i-2] + nums[i])——跳过这家,或者抢它再加上到两格之前的最优。两个变量(pre、prepre)以 O(1) 空间走完数组。一旦你在这里看出 Fibonacci 的窗口,「往回看两步」的依赖模式就一眼可辨了。

双序列 DP:一切都变成网格

当输入是两个序列、答案取决于把它们对齐时,状态就升到二维:网格上的 dp[i][j],i 索引第一个序列,j 索引第二个。转移几乎总是读三个邻居——左上、上、左。

LC 72 Edit Distance 是网格的典范:把 word1 变成 word2 的最少 insert/delete/replace 次数。定义 dp[i][j] = word1 前 i 个字符与 word2 前 j 个字符之间的编辑距离。第一行和第一列是白给的(把一个串变成 "" 每个字符一次 delete,反之亦然)。然后每个方向都有含义:上 = delete,左 = insert,左上 = replace。当前字符相等就白拿左上,否则取三者最小再加一。

public int minDistance(String word1, String word2) {
    int l1 = word1.length(), l2 = word2.length();
    int[][] dp = new int[l1 + 1][l2 + 1];
    for (int i = 0; i <= l1; i++) dp[i][0] = i;   // 删 i 个字符变成 ""
    for (int j = 0; j <= l2; j++) dp[0][j] = j;   // 从 "" 插入 j 个字符

    for (int i = 1; i <= l1; i++) {
        for (int j = 1; j <= l2; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];        // 字符相等——直接拿左上
            } else {
                int replace = dp[i - 1][j - 1];
                int delete  = dp[i - 1][j];
                int insert  = dp[i][j - 1];
                dp[i][j] = Math.min(replace, Math.min(delete, insert)) + 1;
            }
        }
    }
    return dp[l1][l2];
}

因为 dp[i][j] 只依赖上一行加上刚算出来的左边一格,网格能压到 O(n) 空间——一个一维数组加一个保存的 prev 值,和 Fibonacci 那次降维一模一样。

这张网格无处不在:

• LC 161 One Edit Distance——一个轻量表亲,不用建表就能解。走到第一个不同的字符,然后分三种情况:长度相等 → 替换后剩下的必须匹配;word1 更长 → 在 word1 里跳一个字符;word2 更长 → 在 word2 里跳一个。当心 i+1 越界。
• 变成回文的最少步数——对每个切点,把右半 reverse 后对左半跑 Edit Distance。网格成了一次扫描里的子过程。
• LC 115 Distinct Subsequences——数 T 作为 S 的子序列出现多少次。网格 mem[i][j] = T[0..i) 在 S[0..j) 中出现的次数;第一行全 1(空串作为子序列恰好出现一次),第一列 0。若 S[j]==T[i] 就把「用这个字符」加上「跳过它」(mem[i][j] + mem[i+1][j]),否则继承跳过那一项。
• LC 97 Interleaving String——s3 是不是 s1 和 s2 的交错?想象一张以 s1、s2 为轴的网格;答案就是能否从 (0,0) 走到 (len1, len2)。三种解法都行——网格上 BFS、带 visited 集合的 DFS,或者干净的 dp[i][j](把「从上面来且匹配 s1」和「从左边来且匹配 s2」做 OR)。

同一节课里有一道字符串「外来户」值得提一句:LC 187 Repeated DNA Sequences 根本不是 DP——它是滚动哈希 / bitmask,滑一个 10 字符窗口,每个碱基用两位编码,于是每个窗口就是一个可以 O(1) 查表的 int。工具不同,但驱动 DP 的「复用上一次计算」的直觉是一样的。

Word Break:DP 判定,DFS 枚举

LC 139 Word Break 问一个 yes/no——s 能不能被切成字典里的词?——这是教科书式的 true/false DP。定义 dp[i] = 「长度为 i 的前缀能否被切分」,dp[0] = true(空前缀)。然后 dp[i] 为真当且仅当存在切点 j 使 dp[j] 为真且 s[j..i) 在字典里。

public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);   // O(1) 查询,而不是 List 上的 O(n)
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;                                   // 空前缀永远可切
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;                             // 找到一个合法切法就够了
            }
        }
    }
    return dp[s.length()];
}

LC 140 Word Break II 只改了一个词——「返回所有句子」——而这个词让 DP 失效。这正是开头那句「DP 给值不给方案」的极限:布尔表列不出路径。解法是带记忆化剪枝的 DFS:从每个下标递归,拼上每个匹配的词,并保留一个 hasResult[] 标记,一旦知道某个下标走不通,就再也不去探它。DP 剪掉决策,DFS 重建证据。

贪心何时优于 DP

贪心是一门「认准局部最优、绝不回头」的纪律。它的前提很严格,值得说出来:只有当每一步局部最优选择都能被证明导致全局最优时,贪心才成立。这个条件成立时,整张表都可以跳过。

LC 55 Jump Game——每个格子给出最大跳跃长度,能不能到最后一格?三层解法讲完整个故事。朴素递归尝试每一跳,O(分叉ⁿ)。布尔 DP 把每个下标标为「若有任何能跳到它的下标可达则它可达」,大致 O(n²)。但贪心洞察把它塌到 O(n):从左往右扫,跟踪目前能到的最远下标;如果你的位置一旦超过这个 reach 就失败,如果 reach 盖住了最后一格就成功。你从不决定往哪跳——只看最远能到哪。

LC 45 Jump Game II 问最少跳几次。O(n²) 的 DP(dp[i] = 从 i 到终点的最少跳数)能做,但 O(n) 贪心是一个伪装的分层 BFS:每一「跳」是一层前沿,只有当前层耗尽时才推进层边界。

public int jump(int[] nums) {
    int steps = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i < nums.length - 1; i++) {   // 到最后一格前就停
        farthest = Math.max(farthest, i + nums[i]);   // 拓宽当前前沿
        if (i == curEnd) {                            // 这一跳的 reach 耗尽
            steps++;                                  // 再提交一跳
            curEnd = farthest;                        // 它的 reach 成为新的层边界
        }
    }
    return steps;
}

切绳子问题(把一段绳子切成整数段,最大化各段乘积)也走了同样的「先 DP 再贪心」这一跳。DP 是老实的——dp[i] = 长度 i 的最优乘积,枚举每个首刀 j <= i/2 取 max(j, dp[j]) * max(i-j, dp[i-j])——O(n²)。但一个数学观察终结了它:和固定要让乘积最大,因子越平均越好,而在整数下切成 3 最优。于是贪心答案就是不断剥 3(把最后剩的 2 或 4 整段留住),给出 O(n):

• 显式处理 n = 2 和 n = 3(至少切一刀 → n-1)。
• 当 n > 4 时,减去 3,结果乘以 3。
• 最后把剩下的(2、3 或 4)乘进去。

笔记里贪心名人堂的其他成员——Candy、Gas Station——都遵循同一条试金石:先证明局部规则逼出全局最优,再放心用。只要能构造出一个局部好、全局输的反例,贪心就是错的工具,老老实实退回 DP。

刷题清单