多维动态规划概述
一维 DP 已经无法满足复杂的算法问题。当问题涉及 两个维度的变化（如二维网格上的移动、两个字符串的比较）时，我们需要引入多维 DP，通常用二维数组 dp[i][j] 来存储状态。
多维 DP 的常见场景：
- 网格路径问题：在二维矩阵中从左到右/从上到下移动（62、64）。
- 双序列匹配问题：比较两个字符串的公共子序列、编辑距离（1143、72）。
- 区间问题：在字符串内部逐步扩展（5）。
多维 DP 的核心挑战在于 状态维度的设计 和 填表顺序（逐行、逐列、对角线）。
LeetCode 热门 100 题中，有五道经典多维 DP 题：62. 不同路径、64. 最小路径和、5. 最长回文子串、1143. 最长公共子序列、72. 编辑距离。下面逐一拆解。
1. 不同路径（LeetCode 62）
题目：一个机器人位于 m×n 网格的左上角，每次只能向下或向右移动一步，到达右下角共有多少条不同路径？
暴力法：DFS 回溯，O(2^(m+n))，指数爆炸。
二维DP思路：到达 (i, j) 的路径数等于到达 (i-1, j) 和 (i, j-1) 的路径数之和（只能从上方或左方来）。
状态定义：dp[i][j] 表示从起点到达 (i, j) 的路径数。
状态转移：dp[i][j] = dp[i-1][j] + dp[i][j-1]。
初始化：第一行和第一列均为 1（只能直走）。
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
空间优化：只用一维数组滚动更新。
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j-1];
}
}
return dp[n-1];
}
复杂度：时间 O(m*n)，空间 O(n)（优化后）。
2. 最小路径和（LeetCode 64）
题目：给定 m×n 网格（非负整数），找一条从左上到右下的路径，使路径上的数字总和最小（只能向下或向右移动）。
状态定义：dp[i][j] 表示从起点到达 (i, j) 的最小路径和。
状态转移：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。
初始化：dp[0][0] = grid[0][0]；第一行和第一列分别累计。
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m-1][n-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] = grid[i][j] + Math.min(dp[j], dp[j-1]);
}
}
return dp[n-1];
}
复杂度：时间 O(m*n)，空间 O(n)。
关键点：注意初始化边界值，递推时取上方和左方的最小值。
3. 最长回文子串（LeetCode 5）
题目：给定字符串 s，找出其中最长的回文子串。
二维DP思路：区间 DP，用 dp[i][j] 表示子串 s[i..j] 是否为回文。
状态定义：dp[i][j] = true 当且仅当 s[i] == s[j] 且 (j-i < 2 或 dp[i+1][j-1] == true)。
状态转移：长度从 1 到 n 递增，确保子问题已计算。
public String longestPalindrome(String s) {
int n = s.length();
if (n < 2) return s;
boolean[][] dp = new boolean[n][n];
int start = 0, maxLen = 1;
for (int i = 0; i < n; i++) dp[i][i] = true;
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j)) {
if (len == 2 || dp[i+1][j-1]) {
dp[i][j] = true;
if (len > maxLen) {
maxLen = len;
start = i;
}
}
}
}
}
return s.substring(start, start + maxLen);
}
复杂度：时间 O(n²)，空间 O(n²)。
关键点：DP 填表顺序依赖区间长度；也可以使用中心扩展（空间 O(1)），但 DP 解法是多维区间 DP 的典型代表。
4. 最长公共子序列（LeetCode 1143）
题目：给定两个字符串 text1 和 text2，返回它们的最长公共子序列的长度（不要求连续）。
状态定义：dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的 LCS 长度。
状态转移：
- 若 text1[i-1] == text2[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 longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
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];
}
空间优化：滚动数组（只用两行或一行）。
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[] dp = new int[n+1];
for (int i = 1; i <= m; i++) {
int prev = 0;
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (text1.charAt(i-1) == text2.charAt(j-1)) {
dp[j] = prev + 1;
} else {
dp[j] = Math.max(dp[j], dp[j-1]);
}
prev = temp;
}
}
return dp[n];
}
复杂度：时间 O(m*n)，空间 O(n)。
关键点：注意 dp 中 prev 保存的是左上角的值（即上一轮的 dp[j-1]），避免被覆盖。
5. 编辑距离（LeetCode 72）
题目：给定两个单词 word1 和 word2，计算将 word1 转换成 word2 所需的最少操作数（插入、删除、替换）。
状态定义：dp[i][j] 表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作数。
状态转移：
- 若 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]
- 否则：dp[i][j] = 1 + min(dp[i-1][j]（删除）, dp[i][j-1]（插入）, dp[i-1][j-1]（替换）)
初始化：dp[i][0] = i（删除所有字符），dp[0][j] = j（插入所有字符）。
public int minDistance(String word1, String word2) {
int m = word1.length(), 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];
}
空间优化：滚动数组（一维）。
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[] dp = new int[n+1];
for (int j = 0; j <= n; j++) dp[j] = j;
for (int i = 1; i <= m; i++) {
int prev = dp[0];
dp[0] = i;
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (word1.charAt(i-1) == word2.charAt(j-1)) {
dp[j] = prev;
} else {
dp[j] = 1 + Math.min(dp[j], Math.min(dp[j-1], prev));
}
prev = temp;
}
}
return dp[n];
}
复杂度：时间 O(m*n)，空间 O(n)。
关键点：编辑距离是最全面的双序列 DP 模型，涵盖了增删改三种操作，理解它对后续其他字符串 DP 题有极大帮助。
五题对比与分类
| 题目 | 类型 | 维度含义 | 转移方向 | 空间优化难度 |
|---|---|---|---|---|
| 62. 不同路径 | 网格路径 | (行, 列) | 上方+左方 | 易（一维） |
| 64. 最小路径和 | 网格带权路径 | (行, 列) | 上方/左方取min | 易（一维） |
| 5. 最长回文子串 | 区间DP | (左边界, 右边界) | 由内向外扩展 | 难（依赖对角线） |
| 1143. 最长公共子序列 | 双序列匹配 | (第一个串位置, 第二个串位置) | 匹配/不匹配两种分支 | 中（滚动数组需保留左上角） |
| 72. 编辑距离 | 双序列带操作 | (第一个串位置, 第二个串位置) | 三种操作取min | 中（同上） |
共同本质：二维 DP 的核心都是 构建二维表格，根据相邻状态递推。网格题依赖左上+上方+左方；区间题依赖内部小区间；双序列题依赖左上、上、左。
不同侧重：
- 网格题（62、64）：填表顺序固定（从左到右，从上到下）。
- 区间题（5）：填表顺序按长度递增。
- 双序列题（1143、72）：填表顺序按字符串位置递增（行/列）。
总结：多维DP的核心心法
多维DP是解决多因素决策问题的利器，核心是定义清晰的状态维度和转移规则。填表顺序决定了子问题是否提前就绪，空间优化常常可以用滚动数组降至一维。
应用多维DP的通用步骤：
- 分析变量个数：问题中有几个独立变化的因素（如两个字符串的位置、矩阵的行列、区间左右端点）。
- 定义dp数组：根据变量个数选择维度，明确每个维度的含义。
- 推导转移方程：找到当前状态与"前一步"或"子区间"的关系，尤其注意边界条件。
- 确定填表顺序：
- 矩阵路径：按行或按列。
- 区间DP：按区间长度递增。
- 双序列：按字符串位置递增。
- 空间优化：如果当前状态只依赖于上一行/上一列，可用滚动数组降低空间复杂度。