Go back

LeetCode Hot 100——多维动态规划篇（路径、回文、编辑距离）

LeetCode Hot 100 · 多维动态规划篇

「多维动态规划」这个名字听起来唬人，其实本质就是状态需要两个或更多下标来描述的 DP——最常见的是 dp[i][j] 这种二维状态。它和普通一维 DP 的唯一区别是：状态转移时可能同时依赖「上方」和「左方」，所以你需要格外注意初始化边界和遍历顺序。

这一篇覆盖 Hot 100 里的 5 道经典题：

  1. 62. 不同路径 —— 路径计数，二维 DP 入门
  2. 64. 最小路径和 —— 路径最值，原地 DP 空间优化
  3. 5. 最长回文子串 —— 中心扩展 + 区间 DP
  4. 1143. 最长公共子序列 —— 双串 DP 模板
  5. 72. 编辑距离 —— 双串 DP 天花板

前两题是「网格路径」模型，后三题是「字符串」模型。吃透这 5 道，二维 DP 的骨架就立起来了。每道题我都按「题意 → 难点易错点 → 暴力 → 最优 → 多解法对比 → CodeTop 变体」的结构来拆，重点放在状态怎么定义、转移怎么推、边界怎么初始化这三件事上。

#62 不同路径

题意

机器人在一个 m x n 网格的左上角，每次只能向右或向下移动一步，问到达右下角总共有多少条不同的路径。

输入：m = 3, n = 7
输出：28

难点与易错点

题目本质：二维 DP 路径计数，dp[i][j] = dp[i-1][j] + dp[i][j-1]（从上方来 + 从左方来）。

现实类比：迷宫计数。到达每个格子的路数 = 从上边来的路数 + 从左边来的路数，就像分叉路口的汇流——每条路都把自己的「流量」累加进当前路口。

解法一：暴力 / 直观

最直观的想法是递归 DFS：从 (0,0) 出发，每一步都尝试向下和向右两个方向，走到终点就记 1 条。

class Solution {
    public int uniquePaths(int m, int n) {
        return dfs(0, 0, m, n);
    }

    // 从 (i, j) 走到右下角的路径数
    private int dfs(int i, int j, int m, int n) {
        if (i == m - 1 && j == n - 1) return 1; // 到达终点，算一条路径
        if (i >= m || j >= n) return 0;         // 越界，此路不通
        return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n); // 向下 + 向右
    }
}

瓶颈在哪：存在海量重复子问题——dfs(i, j) 会被从不同路径多次访问并重复计算，例如 dfs(1,1) 同时被 dfs(0,1) 和 dfs(1,0) 调用。这正是可以用 DP 记忆化的信号。

解法二：优化 / 最优

二维 DP 推导（先想清楚状态，再谈空间优化）：

空间优化：观察发现计算第 i 行时只用到第 i-1 行，于是可以用一维数组滚动。更新时 dp[j] 的旧值就是「上方」dp[i-1][j]，dp[j-1] 刚被更新的值就是「左方」dp[i][j-1]，一行代码 dp[j] += dp[j-1] 就完成了转移。

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        // 初始化：第一行每个格子只有 1 条路径
        for (int j = 0; j < n; j++) dp[j] = 1;

        // 从第 2 行开始滚动
        for (int i = 1; i < m; i++) {
            // 从左到右遍历，dp[j] 旧值 = 上方，dp[j-1] 新值 = 左方
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
}

复杂度逐步推导：

💭 思考：二维 DP 为什么能滚成一维，dp[j] += dp[j-1] 这一行凭什么同时代表「上方 + 左方」？——先看二维转移 dp[i][j] = dp[i-1][j] + dp[i][j-1]，它只依赖上一行和本行的前一个。滚动时用一维数组复写：dp[j] 还没更新前的旧值就是「上一行的 dp[i-1][j]」（上方），dp[j-1] 刚更新过的新值就是「本行的 dp[i][j-1]」（左方）。所以一行 dp[j] += dp[j-1] 就把两个方向都加上了。看到「网格路径 DP 且只依赖上一行」这个信号，就想到「滚动数组 + 从左到右遍历」——但必须正序，否则 dp[j-1] 还是旧值就错。

多解法对比

解法时间复杂度空间复杂度适用场景
递归 DFSO(2^(m+n))O(m+n)仅供理解递归思想，不可用于实际
二维 DPO(m×n)O(m×n)直观易懂，适合讲解状态转移
一维滚动 DPO(m×n)O(n)本题最优，面试推荐
组合数 C(m+n-2, m-1)O(min(m,n))O(1)无障碍、只求路径数时的数学捷径

本题约束下（m, n ≤ 100，答案保证在 int 内），一维滚动 DP 的 O(m×n) 时间完全够用，且代码短、不易错，是面试首选。组合数解法虽然更快，但一是容易溢出，二是无法扩展到「有障碍物」的变体，属于锦上添花，可作为加分项口述。

CodeTop 变体

#64 最小路径和

题意

给一个 m x n 的网格 grid，每个格子是一个非负整数。从左上角走到右下角（只能向右或向下），求路径上所有数字之和的最小值。

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7（路径 1→3→1→1→1）

难点与易错点

题目本质：二维 DP 最优路径，dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])，边界独立处理。

现实类比：最省钱路线导航。到达每个路口的最低消费 = 这个路口本身的费用 + 从上方或左方过来的最小消费中取较小者。

解法一：暴力 / 直观

暴力做法同样是递归枚举所有路径，取最小的路径和。

class Solution {
    public int minPathSum(int[][] grid) {
        return dfs(grid, 0, 0);
    }

    private int dfs(int[][] grid, int i, int j) {
        int m = grid.length, n = grid[0].length;
        if (i == m - 1 && j == n - 1) return grid[i][j]; // 到终点，直接返回本格值
        if (i >= m || j >= n) return Integer.MAX_VALUE;  // 越界视为不可达
        return grid[i][j] + Math.min(dfs(grid, i + 1, j), dfs(grid, i, j + 1));
    }
}

瓶颈在哪：和 62 一样，dfs(i, j) 被大量重复调用，每条从起点到 (i,j) 的前缀路径都会重新递归一遍子树。需要用 DP 把「到每个格子的最小和」缓存下来。

解法二：优化 / 最优

二维 DP 推导（让 grid 本身充当 dp 数组，原地修改）：

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        // 初始化第一行：只能从左方来，累加
        for (int j = 1; j < n; j++) grid[0][j] += grid[0][j - 1];
        // 初始化第一列：只能从上方来，累加
        for (int i = 1; i < m; i++) grid[i][0] += grid[i - 1][0];

        // 内部格子：取上方与左方的较小者
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }
}

复杂度逐步推导：

多解法对比

解法时间复杂度空间复杂度适用场景
递归 DFSO(2^(m+n))O(m+n)理解用，不可上生产
二维 DP（新开数组）O(m×n)O(m×n)不允许修改输入时使用
原地 DPO(m×n)O(1)本题最优，默认推荐

本题约束下，时间上 O(m×n) 已经是最优（每个格子至少要访问一次），空间上用原地修改做到 O(1)，无可再压。选原地 DP 既快又省，代码还短。唯一的代价是破坏输入 grid，如果面试官要求不改输入，退回到「新开一维滚动数组」即可，复杂度变为 O(n) 空间。

CodeTop 变体

#5 最长回文子串

题意

给一个字符串 s，返回其中最长的回文子串（回文即正读反读都相同）。

输入：s = "babad"
输出："bab"（"aba" 也是合法答案）

难点与易错点

题目本质：中心扩展法——以每个字符（奇数长度）和每两个相邻字符（偶数长度）为中心，向两边扩展找最长回文。

现实类比：水波扩散找最大镜像区。在每个位置投石激起波纹，从中心向两侧只要字符相等就继续扩，记录下最大的波纹范围。

解法一：暴力 / 直观

枚举所有子串的起点 i 和终点 j，逐一判断是否回文，取最长。

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String ans = "";
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // 只判断比当前答案更长的子串，剪枝
                if (j - i + 1 > ans.length() && isPalindrome(s, i, j)) {
                    ans = s.substring(i, j + 1);
                }
            }
        }
        return ans;
    }

    private boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            l++; r--;
        }
        return true;
    }
}

瓶颈在哪：一是判断回文做了大量重复比较，二是把时间浪费在大量「不可能成为答案」的短子串上。实际上一个更长的回文必然以某个中心向两侧对称展开，我们应该抓住「中心」这个更本质的变量，而不是「起点 + 终点」。

解法二：优化 / 最优

中心扩展法：遍历每个可能的中心，向两侧贪心扩展，直到不再对称。奇数回文的中心是单个字符 (i, i)，偶数回文的中心是两个相邻字符 (i, i+1)，一共 2n - 1 个中心。

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int start = 0, maxLen = 1; // 单个字符本身也是回文

        for (int i = 0; i < n; i++) {
            int odd  = expand(s, i, i);     // 奇数长度：中心是 i
            int even = expand(s, i, i + 1); // 偶数长度：中心是 i 与 i+1
            int len  = Math.max(odd, even);

            if (len > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2; // 由中心和长度反推起点
            }
        }
        return s.substring(start, start + maxLen);
    }

    // 从 (l, r) 向两侧扩展，返回最长回文长度
    private int expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return r - l - 1; // 合法回文区间为 (l, r)，长度为 r - l - 1
    }
}

复杂度逐步推导：

补充：二维 DP 写法（面试官可能追问「用 DP 怎么做」）：

DP 的时间也是 O(n²)，但空间要 O(n²)（可用滚动数组优化到 O(n)），在空间上劣于中心扩展的 O(1)，所以本题面试首选仍是中心扩展。

💭 思考：暴力枚举子串是 O(n³)，怎么一步步想到「中心扩展」？——暴力版枚举「起点 + 终点」O(n²) 种，每种判断回文 O(n)，合计 O(n³)。观察：一个回文串必然以某个中心向两侧对称，所以我们真正该枚举的变量是「中心」而不是「起点 + 终点」。中心只有 2n - 1 个（奇数中心是单个字符、偶数中心是相邻两个字符），每个中心向外扩展直到不对称，总操作量 O(n²)。看到「最长回文子串 / 只求最值不需求所有区间」这个信号，就选中心扩展（空间 O(1)）；只有当题目需要「任意区间是否回文」的布尔信息（如分割回文串）时，才值得开区间 DP 表。

多解法对比

解法时间复杂度空间复杂度适用场景
暴力枚举O(n³)O(1)仅供对比，不可用
二维区间 DPO(n²)O(n²)需要「是否回文」的布尔信息时（如回文分割、计数）
中心扩展O(n²)O(1)本题最优，只求最长回文子串
Manacher 算法O(n)O(n)字符串极长、要求严格线性时的进阶算法

本题约束下（n ≤ 1000），中心扩展的 O(n²) 已足够，空间 O(1) 是最省的，代码也最简洁，是面试首选。Manacher 是加分项，能说出「可以线性」即可，不必现场手写。

CodeTop 变体

#1143 最长公共子序列

题意

给定两个字符串 text1 和 text2，返回它们最长公共子序列（LCS）的长度。子序列不要求连续，但相对顺序必须保持一致；不存在公共子序列时返回 0。

输入：text1 = "abcde", text2 = "ace"
输出：3（"ace"）

难点与易错点

题目本质：经典二维 DP，dp[i][j] 表示 text1[0..i-1] 与 text2[0..j-1] 的 LCS；末尾字符相等则 dp[i-1][j-1]+1，否则 max(dp[i-1][j], dp[i][j-1])。

现实类比：两段 DNA 序列比对。逐步看每对字符是否相同，相同就把公共链延伸一位，不同就看舍弃哪条链的末尾更划算——保留公共部分更长的那个方向。

解法一：暴力 / 直观

递归枚举：从两个字符串末尾往前看，末尾相同就都取、不同就分别舍弃一个取较大。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        return dfs(text1, text2, text1.length(), text2.length());
    }

    // 返回 text1[0..i-1] 与 text2[0..j-1] 的 LCS
    private int dfs(String a, String b, int i, int j) {
        if (i == 0 || j == 0) return 0; // 任一为空串，LCS 为 0
        if (a.charAt(i - 1) == b.charAt(j - 1)) {
            return dfs(a, b, i - 1, j - 1) + 1; // 末尾相同，一起取
        }
        return Math.max(dfs(a, b, i - 1, j), dfs(a, b, i, j - 1)); // 舍弃一个末尾
    }
}

瓶颈在哪：dfs(i, j) 会被大量重复计算——不同的舍弃路径会收敛到同一个 (i, j) 子问题。这正是「记忆化 / 递推」的经典入场时机。

解法二：优化 / 最优

二维 DP 推导：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        // dp[i][j]：text1 前 i 个字符 与 text2 前 j 个字符 的 LCS 长度
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1; // 末尾匹配，公共序列延伸
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // 舍弃一个末尾
                }
            }
        }
        return dp[m][n];
    }
}

复杂度逐步推导：

💭 思考：两个字符串的问题，为什么状态天然是 dp[i][j]？——先看单串 DP 用 dp[i] 描述「前 i 个字符」就够了；但 LCS 涉及两个字符串的「前缀对」，一个下标表达不了「两边各走到哪」，所以状态必须是二维的 dp[i][j] = 两串前 i、前 j 个字符的 LCS。转移也只看「末尾是否相等」：相等就 dp[i-1][j-1]+1（两个末尾都取），不相等就 max(dp[i-1][j], dp[i][j-1])（舍弃其中一个末尾）。看到「双字符串 + 比较/匹配/对齐」这个信号，第一反应就是「二维前缀 DP」，这是编辑距离、LCS 一整族的统一骨架。

多解法对比

解法时间复杂度空间复杂度适用场景
递归 DFSO(2^(m+n))O(m+n)理解用
二维 DPO(m×n)O(m×n)需要回溯构造 LCS 串时（保留完整表）
一维滚动 DPO(m×n)O(min(m,n))只求长度时的最优空间

本题约束下，O(m×n) 时间是下界（两个字符串的每个字符对几乎都要比较一次），无法更优；空间上二维 → 一维滚动即可。面试时先写二维（清晰、不易错），再口述「可以滚动到一维」，是稳妥节奏。若面试官要求输出具体 LCS 串，则需要保留二维表并回溯。

CodeTop 变体

#72 编辑距离

题意

给两个单词 word1 和 word2，返回把 word1 转换成 word2 所需的最少操作次数。操作有三种：插入一个字符、删除一个字符、替换一个字符。

输入：word1 = "horse", word2 = "ros"
输出：3（horse → rorse（替换 h 为 r）→ rose（删除 r）→ ros（删除 e））

难点与易错点

题目本质：经典二维 DP（Levenshtein 距离），dp[i][j] 表示 word1[0..i-1] 变为 word2[0..j-1] 的最少操作数；字符相等时 dp[i-1][j-1]，否则 min(替换, 删除, 插入) + 1。

现实类比：文字自动纠错。把 word1 变成 word2，逐字符对比看是删、增还是改最划算，用记忆化把每个子问题算一次，避免重复计算。

解法一：暴力 / 直观

递归模拟三种操作：末尾字符相同就一起跳过，不同就分别尝试替换、删除、插入，取最小。

class Solution {
    public int minDistance(String word1, String word2) {
        return dfs(word1, word2, word1.length(), word2.length());
    }

    // 返回 word1[0..i-1] 变 word2[0..j-1] 的最少操作数
    private int dfs(String a, String b, int i, int j) {
        if (i == 0) return j; // a 为空，插入 j 次
        if (j == 0) return i; // b 为空，删除 i 次
        if (a.charAt(i - 1) == b.charAt(j - 1)) {
            return dfs(a, b, i - 1, j - 1); // 末尾相同，跳过
        }
        return 1 + Math.min(dfs(a, b, i - 1, j - 1),   // 替换
                   Math.min(dfs(a, b, i - 1, j),       // 删除
                            dfs(a, b, i, j - 1)));     // 插入
    }
}

瓶颈在哪：三个分支会产生大量重叠子问题，且指数级增长极快，m、n 稍大就不可行。必须用 DP 把 dp[i][j] 缓存起来。

解法二：优化 / 最优

二维 DP 推导：

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        // dp[i][j]：word1 前 i 个字符变 word2 前 j 个字符的最少操作数
        int[][] dp = new int[m + 1][n + 1];

        // 边界初始化：与空串互转的编辑距离
        for (int i = 0; i <= m; i++) dp[i][0] = i; // word1 全删
        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 - 1],   // 替换
                                   Math.min(dp[i - 1][j],       // 删除 word1[i-1]
                                            dp[i][j - 1]));     // 插入 word2[j-1]
                }
            }
        }
        return dp[m][n];
    }
}

复杂度逐步推导：

💭 思考：编辑距离的三种操作，为什么对应「左上 / 上方 / 左方」三个方向？——把状态想成「word1 前 i 个 → word2 前 j 个」，转移就是「怎么缩小到更小的子问题」：替换是把 word1[i-1] 换成 word2[j-1]，两边末尾都消耗掉 → 左上 dp[i-1][j-1]；删除是删掉 word1[i-1]，word1 短一位 → 上方 dp[i-1][j]；插入是在 word1 末尾插一个 word2[j-1]，word2 短一位 → 左方 dp[i][j-1]。记住口诀「左上替换、上方删除、左方插入」，再配合「相等时直接跳过 dp[i-1][j-1]，不要 min+1」和「边界 dp[i][0]=i、dp[0][j]=j」，这套双串 DP 就稳了。

多解法对比

解法时间复杂度空间复杂度适用场景
递归 DFSO(3^(m+n))O(m+n)理解三种操作如何映射到递归
二维 DPO(m×n)O(m×n)本题标准答案，需回溯具体操作序列时
一维滚动 DPO(m×n)O(min(m,n))只求距离、追求极致的空间

本题约束下（m, n ≤ 500），O(m×n) 时间是最优，空间用二维表即可（25 万个 int 也就 1MB 级别），无需强行滚动。选择二维 DP 是因为它把三种操作的语义写得最清晰、最不易错，面试时先把二维写对，再主动说「可以滚动到一维」展示优化意识即可。

CodeTop 变体

总结：五题一张表

题目状态定义转移核心边界空间优化
62. 不同路径dp[i][j] 到该格的路径数dp[i-1][j] + dp[i][j-1]第一行/列全 1一维 O(n)
64. 最小路径和dp[i][j] 到该格的最小和grid[i][j] + min(上, 左)第一行/列累加原地 O(1)
5. 最长回文子串dp[i][j] 区间是否回文中心扩展 / 区间 DP单字符天然回文中心扩展 O(1)
1143. LCSdp[i][j] 两前缀 LCS相等 +1，不等取 max第 0 行/列全 0一维 O(n)
72. 编辑距离dp[i][j] 两前缀最少操作相等跳过，不等 min(替换,删,插)+1dp[i][0]=i、dp[0][j]=j一维 O(n)

一个万能套路：二维 DP 手撕时，永远按「状态定义 → 转移方程 → 边界初始化 → 遍历顺序 → 空间优化」五步走，先写二维保证正确，再滚到一维展示优化。把「网格路径」（62/64）和「双字符串」（1143/72）这两条主线打通，绝大多数二维 DP 面试题都能套进去。

章末提问

  1. 什么时候需要把状态定义成二维 dp[i][j]？ —— 结论先行：当子问题需要「两个独立维度」才能唯一描述时。因为单下标无法同时表达两条主线——LCS/编辑距离的两个字符串前缀、网格的行和列，硬压成一维会丢信息，二维状态天然对应「前 i 个 / 前 j 个」。

  2. 边界初始化到底怎么定，而不是照抄 0？ —— 结论先行：边界是「退化成空串或单边」时的答案，要按题意手工算。因为第一行/列（62/64）只能从一个方向累加、空串的 LCS=0、空串变 word2 要插 j 次（dp[0][j]=j），这些都不靠转移方程推，错了整张表全错。

  3. 遍历顺序为什么有的递增、有的要倒着来？ —— 结论先行：由 dp[i][j] 依赖的邻居位置决定。因为最长回文子串的区间 DP 依赖左下方 dp[i+1][j-1]，所以 i 要从大到小（或按区间长度递增）；而网格路径、LCS、编辑距离只依赖上、左、左上，所以 i、j 递增即可，保证依赖项先算出来。

  4. 二维 DP 怎么降到一维滚动？ —— 结论先行：因为当前行只依赖上一行，所以只需一行数组，用「旧值=上方、新值=左方」原地更新。例如 LCS、编辑距离都能用一行 + 一个保存左上角的临时变量，把空间从 O(mn) 降到 O(min(m,n))。

  5. 最长回文子串为什么选中心扩展而不是区间 DP？ —— 结论先行：因为只求「最长回文子串」时中心扩展空间 O(1)，区间 DP 却要 O(n²)。因为中心扩展把「起点+终点」的 O(n³) 枚举转化为「中心+扩展」的 O(n²)，且不存表；只有需要「任意区间是否回文」的布尔信息（如分割回文串）时，才值得开 DP 表。

Share this post on:
Share this post via WhatsAppShare this post on FacebookShare this post on XShare this post via TelegramShare this post on PinterestShare this post via email
Previous Post
LeetCode Hot 100——技巧篇（位运算、多数投票、原地排序）
Next Post
LeetCode Hot 100——动态规划篇（状态定义、转移方程、背包）