【LeetCode Hot100 多维动态规划】最小路径和、最长回文子串、最长公共子序列、编辑距离

机器人路径问题

给定一个 $(m\times n)$ 的网格，机器人位于左上角（起始点 “Start”），只能向下或者向右移动一步，目标是到达右下角（终点 “Finish”）。求总共有多少条不同的路径？

---

思路

1. 状态定义
   用二维数组 dp[i][j] 表示到达网格中位置 $(i,j)$ 的不同路径数。

2. 状态转移
   由于机器人只能从上方或左侧移动到 $(i,j)$：
   $[dp[i][j]=dp[i-1][j]+dp[i][j-1]]$

3. 初始化

   • 起点：dp[0][0] = 1。
   • 第一行 $(i=0)$上的所有位置只能从左边到达，因此路径数均为 1。
   • 第一列 $(j=0)$上的所有位置只能从上面到达，因此路径数均为 1。

4. 答案
   最终答案为 dp[m-1][n-1]。

代码实现

class Solution {public int uniquePaths(int m, int n) {// 创建一个 m x n 的二维数组 dp，用于记录每个位置的路径数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];}
}

最小路径和问题

给定一个包含非负整数的 $(m\times n)$ 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

---

动态规划思路

我们可以使用动态规划来解决这个问题，定义状态 dp[i][j] 表示从起点 ((0, 0)) 到达位置 ((i, j)) 的最小路径和。

状态转移方程

• 对于位置 $(i,j)$，由于只能从上方 $(i-1,j)$ 或左侧 $(i,j-1)$ 移动过来，因此有：
  $dp[i][j]=grid[i][j]+\min (dp[i-1][j],dp[i][j-1])$

边界条件

• 起点：
  $dp[0][0]=grid[0][0]$
• 第一行：
  只能从左侧移动，所以：
  $dp[0][j]=dp[0][j-1]+grid[0][j]\text{(对于 }j\ge 1\text{)}$
• 第一列：
  只能从上面移动，所以：
  $dp[i][0]=dp[i-1][0]+grid[i][0]\text{(对于 }i\ge 1\text{)}$

---

代码实现

下面是基于上述思路的 Java 代码实现：

class Solution {public int minPathSum(int[][] grid) {int m = grid.length;int n = grid[0].length;// 创建 dp 数组，dp[i][j] 表示到达 (i, j) 的最小路径和int[][] dp = new int[m][n];// 初始化起点dp[0][0] = grid[0][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++) {dp[i][0] = dp[i - 1][0] + grid[i][0];}// 填充 dp 数组的剩余部分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];}
}

最长回文子串

给定一个字符串 s，找出 s 中最长的回文子串。

---

思路

我们可以利用动态规划来解决该问题。设 dp[i][j] 表示子串 s[i...j] 是否为回文。状态转移方程为：

$dp[i][j]=(s[i]==s[j])\&\&(j-i<3\text{ 或 }dp[i+1][j-1])$

具体说明如下：

• 当 s[i] 和 s[j] 不相等时，s[i...j] 不是回文，故 dp[i][j] = false。
• 当 s[i] 和 s[j] 相等时：
  • 如果子串长度小于等于 3（即 j - i < 3），那么 s[i...j] 一定是回文，因为此时中间最多只有一个字符。
  • 如果子串长度大于 3，则需依赖子串 s[i+1...j-1] 是否为回文，即 dp[i+1][j-1]。

在更新过程中，我们记录当前最长回文子串的起始位置和长度，最终返回最长的回文子串。

---

代码实现

class Solution {public String longestPalindrome(String s) {int n = s.length();if (n < 2) return s; // 如果字符串长度小于 2，直接返回 s// dp[i][j] 表示 s[i...j] 是否为回文子串boolean[][] dp = new boolean[n][n];int maxLen = 1;  // 记录最长回文子串的长度int start = 0;   // 记录最长回文子串的起始位置// 所有单个字符都是回文子串for (int i = 0; i < n; i++) {dp[i][i] = true;}// 枚举子串的结束位置 j，从 1 到 n-1for (int j = 1; j < n; j++) {// 枚举子串的起始位置 i，从 0 到 j-1for (int i = 0; i < j; i++) {if (s.charAt(i) == s.charAt(j)) {// 如果子串长度小于等于 3，则必为回文；否则看内部子串是否为回文if (j - i < 3) {dp[i][j] = true;} else {dp[i][j] = dp[i + 1][j - 1];}} else {dp[i][j] = false;}// 如果 dp[i][j] 为 true 且子串长度大于当前记录的最长长度，则更新结果if (dp[i][j] && j - i + 1 > maxLen) {maxLen = j - i + 1;start = i;}}}return s.substring(start, start + maxLen);}
}

最长公共子序列（LCS）

题目描述

给定两个字符串 text1 和 text2，返回它们的 最长公共子序列（LCS）的长度。如果不存在公共子序列，则返回 0。

定义：

• 子序列：从字符串中删除某些字符（也可以不删除），但不改变字符的相对顺序后形成的新字符串。
• 公共子序列：同时属于 text1 和 text2 的子序列。

---

解决方案 —— 动态规划

1. 状态定义

设 dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列的长度。

2. 状态转移方程

• 若 text1[i-1] == text2[j-1]（即当前字符相同）：
  $dp[i][j]=dp[i-1][j-1]+1$
• 若 text1[i-1] != text2[j-1]（即当前字符不同）：
  $dp[i][j]=\max (dp[i-1][j],dp[i][j-1])$
  取两种删除策略的最大值：
  • dp[i-1][j]：删除 text1 的当前字符
  • dp[i][j-1]：删除 text2 的当前字符

3. 初始化

• dp[0][j] = 0（空字符串 text1 和 text2 的最长公共子序列长度为 0）
• dp[i][0] = 0（同理）

4. 代码实现

class Solution {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];}
}

dp 数组大小是 (m+1) × (n+1)，是为了处理空字符串，避免 dp[i-1][j-1] 边界问题。
这样可以统一状态转移方程，减少边界检查，提高代码的可读性和稳定性。

编辑距离（Edit Distance）

题目描述

给定两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。

可以对一个单词进行如下三种操作：

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

---

解法：动态规划

我们定义 dp[i][j] 为 将 word1[0:i] 转换为 word2[0:j] 所需的最少操作数。

状态转移方程

1. 如果 word1[i-1] == word2[j-1]（即当前字符相同），则不需要额外操作：
   $dp[i][j]=dp[i-1][j-1]$

2. 如果 word1[i-1] ≠ word2[j-1]（即当前字符不同），可以执行三种操作：

   • 插入字符（dp[i][j-1] + 1）：相当于在 word1 插入 word2[j-1]，这样 word1[0:i] 变成 word2[0:j]。
   • 删除字符（dp[i-1][j] + 1）：相当于删除 word1[i-1]，这样 word1[0:i-1] 变成 word2[0:j]。
   • 替换字符（dp[i-1][j-1] + 1）：将 word1[i-1] 变成 word2[j-1]，这样 word1[0:i] 变成 word2[0:j]。

   取三者最小值：
   $dp[i][j]=\min (dp[i-1][j-1]+1,dp[i][j-1]+1,dp[i-1][j]+1)$

边界条件

• dp[0][j] = j（word1 为空，需要插入 j 个字符）
• dp[i][0] = i（word2 为空，需要删除 i 个字符）

---

代码实现

class Solution {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;// 计算 dp 数组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] = Math.min(dp[i - 1][j - 1],  // 替换Math.min(dp[i - 1][j],  // 删除dp[i][j - 1])) + 1; // 插入}}}return dp[m][n];}
}

二维动态规划答题总结

1. 识别动态规划问题

当问题具有以下特征时，可以考虑使用动态规划（Dynamic Programming, DP）：

• 最优子结构（Optimal Substructure）：问题可以拆解成子问题，且子问题的最优解可以构成原问题的最优解。
• 重叠子问题（Overlapping Subproblems）：子问题在递归求解过程中被多次计算。
• 状态转移（State Transition）：能够从小规模问题推导出大规模问题的解。

对于 二维动态规划，通常涉及两个字符串（或两个维度的数据），例如：

• 子序列问题（如最长公共子序列 LCS）
• 子数组/子矩阵问题（如最小路径和、最大乘积子数组）
• 字符串编辑问题（如编辑距离）

---

2. 解决二维 DP 题目的通用步骤

Step 1: 定义 DP 数组

确定 dp[i][j] 的含义，一般是：

• 字符串匹配问题：dp[i][j] 代表 text1[0:i] 和 text2[0:j] 的匹配结果（如最长公共子序列）。
• 路径问题：dp[i][j] 代表到达 grid[i][j] 的最优解（如最短路径）。
• 编辑距离：dp[i][j] 代表 word1[0:i] 变成 word2[0:j] 的最少操作次数。

---

Step 2: 确定状态转移方程

一般来说，状态转移方程由以下情况组成：

1. 字符匹配时的继承状态：如 dp[i][j] = dp[i-1][j-1]（最长公共子序列）。
2. 考虑不同操作的最优值：
   • 取最小值（如 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1）。
   • 取最大值（如 max(dp[i-1][j], dp[i][j-1])）。
   • 取累积值（如 dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])）。

---

Step 3: 初始化边界条件

不同问题的边界初始化方式不同，常见情况：

• 子序列问题：
  • dp[i][0] = 0，因为空串与任何串的 LCS 都是 0。
  • dp[0][j] = 0，因为空串与任何串的 LCS 都是 0。
• 路径问题：
  • dp[0][j] 为前缀和（只能从左走）。
  • dp[i][0] 为前缀和（只能从上走）。
• 编辑距离问题：
  • dp[i][0] = i，表示 word1 变成空串需要 i 次删除。
  • dp[0][j] = j，表示空串变成 word2 需要 j 次插入。

---

Step 4: 计算 DP 数

• 通过 两层循环 计算 dp[i][j]（通常是 O(m × n)）。
• 先遍历 行 或 列，依赖于状态转移方程。

---

Step 5: 优化空间复杂度

通常二维 DP 使用 O(m × n) 的空间，可以优化至 O(n) 甚至 O(1)：

• 滚动数组：用两个数组 prev 和 curr 代替整个 dp 矩阵（适用于 LCS、编辑距离）。
• 原地修改：如果问题允许，我们可以在原数组上修改（适用于路径问题）。

---

3. 典型题目总结

题目	状态定义	状态转移方程	时间复杂度	空间优化
最长公共子序列（LCS）	dp[i][j] 代表 text1[0:i] 和 text2[0:j] 的 LCS 长度	dp[i][j] = dp[i-1][j-1] + 1（匹配）或 max(dp[i-1][j], dp[i][j-1])	O(m × n)	O(n)
编辑距离（Edit Distance）	dp[i][j] 代表 word1[0:i] 变成 word2[0:j] 的最少操作次数	dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1	O(m × n)	O(n)
最小路径和	dp[i][j] 代表到达 grid[i][j] 的最小路径和	dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])	O(m × n)	O(n)
最长回文子串（中心扩展或 DP）	dp[i][j] 代表 s[i:j] 是否是回文	dp[i][j] = (s[i] == s[j] && dp[i+1][j-1])	O(n²)	O(n²) → O(1)

---