动态规划 II

第一节 DP 课教你的是:动态规划不过是配了一张记忆化表的数学归纳法。这第二课,就是把这个观念拿去做压力测试:状态升到二维,转移不再是一行代码,真正的难点从「递推公式是什么」转移到「状态是什么」。我们从网格路径 DP 出发,经过 Maximal Square、把 O(n⁶) 暴力压成 O(n³) 的最大子矩阵和流水线、几道序列经典题(Decode Ways、用 Catalan 数计数的 BST),最后落到打家劫舍三部曲。中途还会拐进两道看着像 DP、其实是在考「怎么预处理网格」的矩阵题——Surrounded Regions 和最大空心正方形。

DP 心法:记忆化就是归纳法

这节课开场先把第一节 DP 课的定义重新锚定一遍。每一个 DP 解法的关键都是记忆化存储。结构上,DP 就是一个数学归纳法证明:你先立一个 base case——f(0),再写一条 induction rule(归纳规则)把你从 f(k) 带到 f(k+1)。没有比这更玄的东西。记忆化表不过是你缓存每个 f(k) 的地方,让它永远不被重算。

这个视角立刻把常被混为一谈的 DP 和普通 recursion 区分开:

最后一行是货真价实的面试陷阱,笔记里说得很直白:DP 给不出具体方案,只有最优值或方案数。如果面试官问的不是「有多少条路径」而是「打印出一条路径」,你要么补上 parent 指针,要么改用 recursion/回溯的写法。搞清楚自己到底被问了哪种,就赢了一半。

DP 解题四步法

下面每道题都靠同样的四步(其实是五步)搞定。面试时把这几步说出来——结构本身和代码一样值钱:

1. Definition(定义)——精确说出 dp[i] 或 dp[i][j] 的含义。题目就是在这一步被解决或被葬送。
2. Base case / start(起点)——归纳赖以起步的种子值。
3. Induction rule / 转移——状态转移方程,把当前下标和以前的关联起来。要问自己:i 依赖前一步、前几步,还是全部之前的状态?
4. Termination / answer(答案)——最终答案落在哪个格子(常是 dp[n],有时是一个滚动 max)。
5. Optimization(优化)——正确版跑通后,再压表(滚动数组)、复用空间。

而要在第一时间认出「这是道 DP 题」,笔记给了四个关键词提示:Max/Min、Longest/Shortest、Yes/No(可行性)、Count 方案数。它还把 DP 题归成四种反复出现的形态,是贯穿整节课的一张地图:

• Sequence DP(序列)——一个数组/字符串,dp[i] 定义在前缀上(Decode Ways、打家劫舍)。
• Two-sequence DP(双序列)——两个字符串,dp[i][j] 定义在两个前缀上(Distinct Subsequences、Interleaving String)。
• Matrix DP(矩阵)——一张网格,dp[i][j] 定义在单元格上(Min Path Sum、Maximal Square)。
• Backpack / 背包——以容量为下标的状态,经典的重量-价值取舍。

网格路径 DP:Min Path Sum 与 Unique Paths

LC 64 Minimum Path Sum 是教科书级的入门,而关键词 minimum 就是信号——它在喊 DP。把 dp[i][j] 定义为从 grid[0][0] 走到 grid[i][j] 的最小路径和。因为只能往右或往下走,一个格子要么从上方到、要么从左边到,于是转移是一个干净的二选一取 min:

public int minPathSum(int[][] grid) {
    int[][] dp = new int[grid.length][grid[0].length];
    dp[0][0] = grid[0][0];
    for (int i = 1; i < grid.length; i++)
        dp[i][0] = dp[i-1][0] + grid[i][0];        // 第一列:只能从上方来
    for (int j = 1; j < grid[0].length; j++)
        dp[0][j] = dp[0][j-1] + grid[0][j];        // 第一行:只能从左边来

    for (int i = 1; i < grid.length; i++)
        for (int j = 1; j < grid[0].length; j++)
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
    return dp[grid.length-1][grid[0].length-1];
}

LC 62 Unique Paths 把运算从 min 换成 +:dp[i][j] = dp[i-1][j] + dp[i][j-1] 数的是到达某格的方案数。这里就用上了笔记力推的第一个优化——滚动数组。因为每行只需要上一行,你只保留一个长度 n 的一维 dp,原地更新:dp[j] += dp[j-1]。旧的 dp[j] 就是「从上方来」的值,刚更新过的 dp[j-1] 就是「从左边来」的值。一行代码,O(n) 空间。

LC 63 Unique Paths II 加了障碍物,滚动数组用一个分支就搞定:逐格遍历,一旦 obstacleGrid[i][j] == 1 就把 dp[j] = 0(没有路径能穿墙);否则照旧累加 dp[j] += dp[j-1]。障碍物只是把那一列的贡献在后续扫描里清零——转移逻辑一点没动。

Maximal Square 与「取三邻最小」的技巧

LC 221 Maximal Square——给定 01 矩阵,求最大全 1 正方形的面积。暴力是个反面教材:枚举每个正方形是 Θ(n⁵),每个矩形 Θ(n⁶),而且反复重复检查同一批格子。DP 用一个极其紧凑的状态抹掉这份冗余。

把 dp[i][j] 定义为以 (i, j) 为右下角的最大全 1 正方形的边长。如果这格是 1,它撑起的正方形受三个邻居——上方、左方、左上斜对角——限制,因为只要有一边短了缺了,就构不成完整正方形。于是取三者最小值再 +1:

public int maximalSquare(char[][] matrix) {
    if (matrix == null || matrix.length == 0
        || matrix[0] == null || matrix[0].length == 0) return 0;

    int row = matrix.length, col = matrix[0].length, max = 0;
    int[][] dp = new int[row][col];
    for (int i = 0; i < row; i++) {           // 第一列作为 base case
        dp[i][0] = matrix[i][0] - '0';
        max = Math.max(max, dp[i][0]);
    }
    for (int j = 0; j < col; j++) {           // 第一行作为 base case
        dp[0][j] = matrix[0][j] - '0';
        max = Math.max(max, dp[0][j]);
    }
    for (int i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            if (matrix[i][j] == '0') dp[i][j] = 0;
            else dp[i][j] = Math.min(dp[i-1][j-1],
                       Math.min(dp[i-1][j], dp[i][j-1])) + 1;
            max = Math.max(max, dp[i][j]);
        }
    }
    return max * max;                          // 边长 → 面积
}

两个值得刻进脑子的细节:答案是整张表上的滚动 max,不是 dp[n-1][m-1](最大正方形可以在任何位置结尾);返回 max * max,因为状态记的是边长,不是面积。matrix[i][0] - '0' 这个惯用法把 char 数字转成对应的 int 值,用来初始化首行首列。

空心正方形的表亲

笔记接着抛出一个更难的近亲:给一张 X/O 网格,求边框全是 1(全 X)的最大空心正方形。暴力对每个角、每个尺寸做螺旋检查,O(n⁴)。聪明的路子是预处理方向连续长度:建一张 hor 表(每格左边连续 1 的个数)和一张 ver 表(每格上方连续 1 的个数),各 O(n²)。然后对每格取 small = min(hor, ver)——这是能保证的右边和下边;再不断缩小 small,直到对应的左边(ver[i][j-small+1])和上边(hor[i-small+1][j])都够长。两张预处理矩阵把 O(n⁴) 搜索压到大约 O(n³):整节课「用空间换时间」母题的一个缩影。

LC 130 Surrounded Regions 顺着同一段矩阵思维搭车出现,虽然它是图遍历题、不是 DP。任何和边界连通的 O 都能存活,其余全翻成 X。诀窍是反过来想:从每个边界上的 O 起做 DFS 或 BFS,把整片与边界连通的区域标成安全(比如 '*' 或 'U'),最后一次扫描把剩下的 O 变 X、把标记的还原回 O。这是经典的「从边界灌水」套路,和 DP 处理网格的方式形成干净的对照。

1 的图案:从一维连续段到加号

一个短小却很有启发的题族,笔记分阶段搭起来。先从一维开始:给 1 1 1 1 0 0 1 0 1 1,求最长连续 1 段。DP 是当前格为 1 时 dp[i] = dp[i-1] + 1,否则 0——得到 1 2 3 4 0 0 1 0 1 2。这个「连续段长度」就是后面一切的原子。

升到二维,目标变成一个加号:一个中心格加上四条等长的 1 臂。朴素做法是对每个中心往四个方向走、取最短臂长——O(n²·n) = O(n³) 时间、O(1) 空间。但预处理四张方向连续长度矩阵(上、下、左、右),每个中心就变成一次 O(1) 查表:O(n²) 时间,代价是 O(4n²) 空间。同一个空间换时间的杠杆,也是撑起空心正方形的同一套四方向预处理。往后笔记还点到更花哨的形状——一个 ⌐ 或 ⊔ 边框——都能靠组合这些方向表解出来。

最大子矩阵和:把二维压成一维

这是本课的智力核心——一道题被讲成从 O(n⁶) 到 O(n³) 的五阶段优化,而且每个阶段都是能复用的技巧。

阶段 1——暴力。一个矩形要四个下标才能钉死,求和又 O(n²):O(n⁴)·O(n²) = O(n⁶)。没救,但它点明了要分开攻击的两块开销。

阶段 2——先想一维。碰二维之前,先回忆一维工具箱。Kadane 算法 O(n) 求最大子数组和:dp[i] = dp[i-1] + arr[i](当 dp[i-1] > 0),否则 arr[i]。而前缀和数组能 O(1) 回答任意区间和:令 dp[i] = sum(0..i),则 sum(i, j) = dp[j] − dp[i-1]。笔记强调一个漂亮的推论:要判断有没有子数组和等于 k,变形成 dp[i] + k = dp[j],用 HashSet/HashMap 查——和 Two Sum 是同一招。

阶段 3 & 4——前缀和上二维。先沿一个方向做前缀和,得到 O(1) 的行和;再对整张矩阵做前缀和。定义 dp[i][j] = 从 (0,0) 到 (i,j) 矩形的和。建表和查询都是容斥:

// 建表:矩形 (0,0)..(i,j) 的和
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i][j];

// 查询:以 A(左上) .. D(右下) 为角的子矩形和
//   A --- B          子矩形 = D - B - C + A
//   |     |        = dp[x][y] - dp[a-1][y] - dp[x][b-1] + dp[a-1][b-1]
//   C --- D          每个矩形求和现在都是 O(1)

有了 O(1) 的矩形求和,暴力降到 O(n⁴)——我们杀掉了内层的 O(n²),但还剩四层角循环。

阶段 5——压两行,再 Kadane。最后一跃借的是阶段 2 的洞见:如果你不需要知道最大子矩形在哪,只要它的值,Kadane 就能用 O(1) 记账替掉 O(n) 扫描。于是固定上边行 a 和下边行 x(有 O(n²) 对),用行前缀和把它俩之间的每一列压成一个值——列和 = prefix[x] − prefix[a-1]——再对这条压扁的一维条跑 Kadane,找最优的左右跨度。总计:O(n²) 预处理 + O(n²) 行对 × O(n) Kadane = O(n³)。从 O(n⁶) 到 O(n³),靠的是把二维问题往它的一维骨架上套。

序列 DP:Decode Ways 与 BST 计数

LC 91 Decode Ways——一个数字串能被解码成字母(A=1 … Z=26)的方案有几种?经典序列 DP:dp[0] = 1(空串有一种解码),dp[1] 取决于第一个数字是否是合法单字符,之后每个位置累加「合法单数字读法」(dp[i-1])加「合法两位数字读法」(dp[i-2])。

public int numDecodings(String s) {
    if (s == null || s.length() == 0) return 0;
    int n = s.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = s.charAt(0) != '0' ? 1 : 0;

    for (int i = 2; i <= n; i++) {
        int one = Integer.parseInt(s.substring(i-1, i));   // 末尾单个数字
        int two = Integer.parseInt(s.substring(i-2, i));   // 末尾两位数字
        if (one >= 1 && one <= 9)  dp[i] += dp[i-1];
        if (two >= 10 && two <= 26) dp[i] += dp[i-2];
    }
    return dp[n];
}

陷阱全在零上:孤零零一个 0 没有单字符解码,而只有 10–26 才算合法两位读法(所以 07 非法)。two 的 >= 10 下界,正是用来否掉带前导零的两位组合。

LC 96 Unique Binary Search Trees 是穿着组合数学外衣的 DP。用 1…n 建 BST,枚举每个值 i 当根;子序列 1…(i-1) 构成左子树、(i+1)…n 构成右子树,各自递归地建。根不同保证树不同。设 G(n) 为长度 n 序列的方案数;选根 i 贡献 G(i-1) · G(n-i)(左右形状的笛卡尔积)。对所有根求和,就得到 Catalan 递推 G(n) = Σ G(k-1)·G(n-k):

public int numTrees(int n) {
    if (n < 2) return 1;
    int[] dp = new int[n + 1];
    dp[0] = 1;                       // 空树
    dp[1] = 1;                       // 单节点
    for (int i = 2; i <= n; i++)
        for (int k = 1; k <= i; k++)
            dp[i] += dp[k-1] * dp[i-k];   // 根为 k:左子树 k-1 个,右子树 i-k 个
    return dp[n];
}

它的姊妹题 LC 95 Unique Binary Search Trees II 要你真正构造出每一棵树,而不只是计数——这恰好就是开篇那条「DP 给数、recursion 给对象」的分界线。LC 95 要用递归:对每个区间返回子树列表,再做左×右组合;而 LC 96 只需要上面那个计数 DP。

打家劫舍 I / II / III

一个三部曲,展示同一条递推如何适配一条线、一个圈、一棵树。核心决策从不改变:在每一家,要么跳过它(保留目前最优),要么抢它并加上两家之前的最优。

// LC 198 — 一排房子,两个滚动变量做到 O(1) 空间
public int rob(int[] nums) {
    int pre = 0, prePre = 0;               // 到 i-1 和 i-2 为止的最优
    for (int x : nums) {
        int cur = Math.max(pre, prePre + x);    // 跳过 x,或抢 x + 两家前的最优
        prePre = pre;
        pre = cur;
    }
    return pre;
}

// LC 213 — 房子围成一圈:首尾相邻,不能都抢
public int robCircular(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    return Math.max(robRange(nums, 0, nums.length - 2),   // 丢掉最后一家
                    robRange(nums, 1, nums.length - 1));  // 丢掉第一家
}

LC 198 是线性 base case——两个变量(pre、prePre)往前滚,不需要数组。LC 213 打家劫舍 II 把房子排成一圈,于是同时抢首和尾就违规了;解法很优雅——把线性解跑两遍,一遍在 [0, n-2],一遍在 [1, n-1],取 max。你不过是在每一遍里各禁掉两个冲突端点之一。

LC 337 打家劫舍 III 把钱搬进二叉树:抢一个节点就跳过它的两个孩子,但可以拿它的四个孙子。这是带记忆化的树上 DP——一个以 TreeNode 为键的 HashMap 缓存每个节点的最优。对一个节点,比较「抢它 + 四个孙子的最优」与「不抢它 + 两个孩子的最优」,存下胜者。和线性版一模一样的「抢或不抢」决策,只是挂在递归上而非循环上。

双序列与区间 DP:三道压轴硬题

课程收尾点了三道更难的题,把同一套机器推进到二维字符串状态——正是区分「能过」和「过得漂亮」的那种题:

• LC 132 Palindrome Partitioning II——把字符串切成回文段的最少切割数。它把布尔的 isPalindrome[i][j] 区间 DP 和一维 cut[i] DP 配对:当 s[j..i] 是回文时,cut[i] = min(cut[j-1] + 1)。两张 DP 表协作。
• LC 115 Distinct Subsequences——数字符串 t 作为 s 的子序列出现了几次。双序列 DP:dp[i][j] = 用 s[0..i) 拼出 t[0..j) 的方案数;字符相等时既取又跳(dp[i-1][j-1] + dp[i-1][j]),否则只跳。
• LC 97 Interleaving String——s3 能否由 s1 和 s2 交错拼成?一个 yes/no 双序列 DP,dp[i][j] 可达当且仅当当前 s3 字符匹配 s1[i-1](来自 dp[i-1][j])或 s2[j-1](来自 dp[i][j-1])。

这三道都是解题配方里的双序列和区间形态——证明只要状态定好,连「硬」DP 也不过是同样的四步,配一张更大的表。

刷题清单