动态规划

1. DP 在做一件什么事

拿爬楼梯说。走到第 $n$ 阶的方法数满足 $f(n) = f(n-1) + f(n-2)$,直接递归是指数级的,因为递归树上同一个 $f(k)$ 会被算非常多遍。DP 的全部内容其实就一句话:把算过的子问题存下来,每个子问题只算一次。

从递归到 DP 有两条等价的路:

1. 记忆化搜索:递归照写,加一个数组挡住重复计算,自顶向下
2. 递推:从最小的子问题开始把表填满,自底向上

递推版爬楼梯,顺手做了滚动变量优化(dp[i] 只依赖前两格,就不开数组了):

public int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;           // a = f(i-2), b = f(i-1)
    for (int i = 3; i <= n; i++) {
        int c = a + b;          // f(i) = f(i-1) + f(i-2)
        a = b;
        b = c;
    }
    return b;
}

一道题能用 DP,通常同时满足三件事:有重叠子问题(递归会重复算)、有最优子结构(大问题的最优解能由子问题的最优解拼出来)、无后效性。无后效性用白话说:只要知道”现在的状态是什么”,就不用关心”这个状态当初是怎么走出来的”,未来只由现在决定。

做题固定四步:状态定义、转移方程、初始化、遍历顺序。我自己的经验,九成的卡壳发生在第一步。状态一旦定义对了,转移方程往往就是把”最后一步有哪几种可能”翻译成代码。

2. 线性 DP:一切从”选或不选”开始

打家劫舍是最干净的入门题。状态定义 dp[i] = 前 i 间房能偷到的最大金额。面对第 i 间房只有两种选择:

• 偷: dp[i-2] + nums[i] (上一间必须跳过)
• 不偷: dp[i-1]
• dp[i] = max(两者)

public int rob(int[] nums) {
    int pp = 0, p = 0;          // pp = dp[i-2], p = dp[i-1]
    for (int x : nums) {
        int cur = Math.max(pp + x, p);
        pp = p;
        p = cur;
    }
    return p;
}

“选或不选”这个分叉是后面所有背包问题的原型,先在这里焊死。

状态定义的两板斧

最大子数组和:子数组必须连续,所以状态得是”以 i 结尾的最大和”,答案在全程取 max。转移只有两种:接上前面(dp[i-1] + nums[i]),或者另起炉灶(nums[i])。

public int maxSubArray(int[] nums) {
    int ans = nums[0], cur = 0;     // cur = 以当前元素结尾的最大和
    for (int x : nums) {
        cur = Math.max(cur + x, x); // 接上前面, 或从我重新开始
        ans = Math.max(ans, cur);   // 答案是所有结尾位置里最好的那个
    }
    return ans;
}

状态不够就加维

乘积最大子数组套上面的模板会推不动:乘一个负数会让最大变最小、最小变最大,只维护一个”最大”信息量不够。解法就是同时维护”以 i 结尾的最大积”和”最小积”两个状态。这题给我的教训可以推广:转移方程写不出来的时候,先怀疑状态里的信息不够,加一维试试。

public int maxProduct(int[] nums) {
    int maxF = nums[0], minF = nums[0], ans = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int mx = maxF, mn = minF;   // 先快照, 避免下面两行互相污染
        maxF = Math.max(nums[i], Math.max(mx * nums[i], mn * nums[i]));
        minF = Math.min(nums[i], Math.min(mx * nums[i], mn * nums[i]));
        ans = Math.max(ans, maxF);
    }
    return ans;
}

3. 0-1 背包:每个物品只能用一次

标准场景:n 个物品各有重量和价值,背包容量有限,每个物品最多拿一次,求能装下的最大价值。Hot 100 里它以判定形式出现:分割等和子集,判断能否挑出一个子集使其和恰好等于 sum / 2。

先写二维,这是最自然的版本

状态 dp[i][j] = 用前 i 个数能否凑出和 j。对第 i 个数 x,选或不选:

• 不选 x: dp[i][j] = dp[i-1][j]
• 选 x: dp[i][j] = dp[i-1][j-x] (剩下的 j-x 只能靠前 i-1 个数凑, x 已经用掉了)

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int x : nums) sum += x;
    if (sum % 2 == 1) return false;
    sum /= 2;

    boolean[][] dp = new boolean[nums.length + 1][sum + 1];
    dp[0][0] = true;                            // 空集能凑出 0
    for (int i = 1; i <= nums.length; i++) {
        int x = nums[i - 1];
        for (int j = 0; j <= sum; j++) {
            dp[i][j] = dp[i - 1][j];            // 不选
            if (j >= x) dp[i][j] |= dp[i - 1][j - x];   // 选
        }
    }
    return dp[nums.length][sum];
}

这个版本没有任何技巧,转移方程就是”选或不选”的逐字翻译。一维写法里所有看起来诡异的东西,都是从它压缩出来的,所以心里存二维,手上写一维,忘了就退回来重推。

压缩成一维:倒序的来历

观察转移方程:第 i 行只用到第 i-1 行,更早的行全是死数据。那就只留一行,每处理一个物品在这行上原地翻新,空间从 $O(n \cdot sum)$ 降到 $O(sum)$。

压缩带来一个新问题。写成 dp[j] |= dp[j-x] 之后,j-x 在 j 的左边,一维数组上它到底存着旧值(上一行)还是新值(本行),完全由遍历方向决定。0-1 背包要的是上一行的旧值,所以必须从右往左,让左边的格子在被读取时还没被本轮改过:

boolean[] dp = new boolean[sum + 1];
dp[0] = true;
for (int x : nums) {
    for (int j = sum; j >= x; j--) {    // 倒序: 保住左边的旧值
        dp[j] |= dp[j - x];
    }
}
return dp[sum];

用一个最小反例看正序错在哪。nums = [2],目标 4,正确答案是凑不出:

正序:

1. j=2 时 dp[2] |= dp[0] 变 true
2. j=4 时 dp[4] |= dp[2], 读到的是刚改过的新值, dp[4] 变 true
3. 相当于把 2 用了两次, 错

倒序:

1. j=4 时 dp[4] |= dp[2], 此时 dp[2] 还是旧的 false
2. j=2 时 dp[2] |= dp[0] 变 true
3. dp[4] = false, 对

一维版还有两个隐藏语义,想通之后代码就透明了:

“不选”去哪了:一维数组里 dp[j] 当前存的就是上一行的值,也就是”不选 x”的结果。不去动它,它就自动保留。|= 是在”不选”的基础上再或一个”选”。

内层为什么到 j >= x 就停:j < x 时物品装不下,只能不选,而不选等于什么都不做,循环直接结束就行,连 if 都省了。

4. 完全背包:物品可以无限用

零钱兑换:硬币每种无限枚,凑出 amount 的最少硬币数。先看二维转移,它和 0-1 背包只差一个下标:

• 0-1: dp[i][j] = min(dp[i-1][j], dp[i-1][j-x] + 1)
• 完全: dp[i][j] = min(dp[i-1][j], dp[i][j-x] + 1),唯一区别在第二项:读的是本行的 dp[i][j-x]

区别的来源:选了一枚 x 之后,凑剩下的 j-x 时还允许继续用 x,所以状态停在第 i 行。压缩到一维后,“本行”意味着要读新值,新值在左边,所以从左往右正序遍历,故意让本轮的更新传播下去:

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);            // 哨兵: 任何合法答案不会超过 amount 枚 1 元
    dp[0] = 0;
    for (int x : coins) {
        for (int i = x; i <= amount; i++) { // 正序: 故意用本行的新值, 实现无限次
            dp[i] = Math.min(dp[i], dp[i - x] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

拿同一组数据(一个数 2,目标 4)对照两个方向,会发现同一种”污染”在两类题里身份完全相反:正序把 2 用了两次,在分割等和子集里是 bug,在零钱兑换里恰好是需求。遍历方向承载语义,这是背包一维写法的核心:

完全平方数就是物品为 $1, 4, 9, 16, \dots$ 的完全背包求最少物品数,和零钱兑换同一个模子。

初始化和哨兵

初始化只看问题的问法,和背包类型无关:

求最小时哨兵别直接用 Integer.MAX_VALUE:dp[i-x] + 1 会溢出成负数,然后被 Math.min 当成最优解捡走。两个惯用替身,Integer.MAX_VALUE / 2(留出加法余量),或者像上面那样用 amount + 1(合法答案的上界,天然溢不了)。

数方案时才有第三个问题:循环谁在外层

求方案数时,“外层物品、内层容量”数出来的是组合(顺序无关,LC 518 零钱兑换 II),“外层容量、内层物品”数出来的是排列(顺序算不同方案,LC 377 组合总和 IV)。这两题在 Hot 100 之外,先记结论。求最值和判可行的题不受这条影响,前面两节可以放心把物品放外层。

5. 网格 DP

不同路径、最小路径和:状态就是坐标,dp[i][j] = 走到格子 (i, j) 的答案。机器人只能往右往下,所以来源只有上方和左方:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] dp = new int[n];                  // 压缩成一行
    dp[0] = grid[0][0];
    for (int j = 1; j < n; j++) dp[j] = dp[j - 1] + grid[0][j];
    for (int i = 1; i < m; i++) {
        dp[0] += grid[i][0];                // 每行第一格只能从上面来
        for (int j = 1; j < n; j++) {
            // dp[j] 还没更新 = 上一行(上方), dp[j-1] 刚更新 = 本行(左方)
            dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);
        }
    }
    return dp[n - 1];
}

注意这里的一维压缩用的是正序:dp[j] 未更新时恰好是上方格子,dp[j-1] 已更新恰好是左方格子,两个依赖都自动拿对。和背包是同一个道理,方向由”我要旧值还是新值”决定,只是这题恰好两种都要,正序刚好各取所需。

6. 双串 DP

两个字符串的题九成套同一个模板:dp[i][j] = s 的前 i 个字符和 t 的前 j 个字符的答案,填一张二维表,每格只看左、上、左上三个邻居。

最长公共子序列:

• s[i-1] == t[j-1]: dp[i][j] = dp[i-1][j-1] + 1 (两边各贡献一个字符)
• 否则: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

编辑距离,同一张表,转移换成三邻居取最小再加一,分别对应替换、删除、插入:

public int minDistance(String s, String t) {
    int m = s.length(), n = t.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;      // t 为空: 只能删 i 次
    for (int j = 0; j <= n; j++) dp[0][j] = j;      // s 为空: 只能插 j 次
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];        // 末位相同, 白嫖
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],           // 替换
                               Math.min(dp[i - 1][j], dp[i][j - 1])); // 删 / 插
            }
        }
    }
    return dp[m][n];
}

一个通用小技巧:表多开一行一列表示空串,下标 i 对应字符 s.charAt(i-1)。空串行列在初始化时一次填好,转移里就不用写任何越界判断。

7. 其他常客

单词拆分:dp[i] = 前 i 个字符能否被字典拆开,枚举最后一个单词断在哪。本质是完全背包判可行,字典里的词可以无限次用。

最长回文子串:区间 DP 的入门形态,dp[l][r] 由 dp[l+1][r-1] 推出,所以遍历要按区间长度从小到大,先短后长。这又是一次”遍历顺序由依赖关系决定”。实际做题中心扩展法更好写,两种都在 Hot 100 代码里。

最长递增子序列:$O(n^2)$ 解法就是第 2 节的”以 i 结尾”板斧;$O(n \log n)$ 的贪心加二分 tail 数组是另一条思路,代码见 Hot 100。

8. 卡壳自救清单

1. 转移方程写不出来:退回记忆化搜索。递归参数就是状态,递归里的分支就是转移,写通之后再翻译成递推
2. 正序倒序记不清:默写一遍二维转移方程,看第二项的行下标是 i-1 还是 i。要上一行就倒序,要本行就正序
3. 答案不对:把整张 dp 表打印出来,和手算的小例子对照,第一个不一致的格子就是转移或初始化的 bug 所在
4. 状态推不动:怀疑信息不够,加一维(乘积最大子数组的最小积就是这么来的)
5. 判可行类背包还有个彩蛋写法:BigInteger 当 bitset 用,dp = dp.or(dp.shiftLeft(x)),整行一起转移,天然免疫方向问题,记得 import java.math.BigInteger

Hot 100 对号入座

延伸阅读

• LeetCode Hot 100 · Java 题解
• 取巧
• Java 刷题 API 与算法模板
• 算法 MindMap