力扣Hot100系列21（Java）——[多维动态规划]总结(不同路径，最小路径和，最长回文子串，最长公共子序列， 编辑距离)

前言

本文记录力扣Hot100里面关于多维动态规划的五道题，包括常见解法和一些关键步骤理解，也有例子便于大家理解

一、不同路径

1.题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

示例 1：

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

示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6

2.代码

classSolution{publicintuniquePaths(intm,intn){// f[i][j]：从左上角(0,0)走到(i,j)的不同路径数int[][]f=newint[m][n];// 初始化第一列：所有(i,0)位置只能向下走到达，路径数为1for(inti=0;i<m;++i){f[i][0]=1;}// 初始化第一行：所有(0,j)位置只能向右走到达，路径数为1for(intj=0;j<n;++j){f[0][j]=1;}// 递推计算每个位置的路径数（从第二行第二列开始）for(inti=1;i<m;++i){for(intj=1;j<n;++j){// 到达(i,j)的路径数 = 从上方(i-1,j)来的路径数 + 从左方(i,j-1)来的路径数f[i][j]=f[i-1][j]+f[i][j-1];}}// 返回走到右下角(m-1,n-1)的路径数returnf[m-1][n-1];}}

3.例子

以m=4、n=3为例

前提
数组f[i][j]：从左上角(0,0)走到(i,j)的不同路径数；仅能向右/向下走，第一行/第一列因单方向可达，路径数全为1；其余位置路径数=上方f[i-1][j]+左方f[i][j-1]。

步骤1：初始化4行3列数组f
定义f[4][3]（行0_3、列02），初始所有值为0。

步骤2：初始化第一列（所有i,0，列固定为0，行遍历0~3）
仅能从上方连续向下走到达，所有位置路径数赋值为1：
f[0][0]=1、f[1][0]=1、f[2][0]=1、f[3][0]=1。

步骤3：初始化第一行（所有0,j，行固定为0，列遍历0~2）
仅能从左方连续向右走到达，所有位置路径数赋值为1：
f[0][0]=1（已赋值）、f[0][1]=1、f[0][2]=1。

步骤4：递推计算所有非第一行/第一列的位置（i从1到3，j从1到2）
第一轮：i=1（第二行），j依次取1、2

• j=1：f[1][1] = f[0][1]（上方） + f[1][0]（左方） = 1+1=2
• j=2：f[1][2] = f[0][2]（上方） + f[1][1]（左方） =1+2=3

第二轮：i=2（第三行），j依次取1、2

• j=1：f[2][1] = f[1][1]（上方） + f[2][0]（左方） =2+1=3
• j=2：f[2][2] = f[1][2]（上方） + f[2][1]（左方） =3+3=6

第三轮：i=3（第四行，最后一行），j依次取1、2

• j=1：f[3][1] = f[2][1]（上方） + f[3][0]（左方） =3+1=4
• j=2：f[3][2] = f[2][2]（上方） + f[3][1]（左方） =6+4=10

步骤5：返回最终结果
取网格右下角位置f[m-1][n-1] = f[3][2]，返回值为10。
即4行3列网格，从左上角走到右下角共有10条不同的路径。

二、最小路径和

1.题目

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12

2.代码

classSolution{publicintminPathSum(int[][]grid){// 获取网格的行数和列数introw=grid.length;//行intcol=grid[0].length;//列// 初始化第一行：第一行只能从左边走过来，路径和累加左边的值for(inti=1;i<col;i++){grid[0][i]+=grid[0][i-1];}// 初始化第一列：第一列只能从上面走下来，路径和累加上面的值for(inti=1;i<row;i++){grid[i][0]+=grid[i-1][0];}// 遍历网格的其他位置（从第二行第二列开始）for(inti=1;i<row;i++){for(intj=1;j<col;j++){// 状态转移：当前位置的最小路径和 = 自身值 + 上方/左方路径和的较小值// 因为只能向下或向右走，所以只需要比较上方和左方的路径和grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]);}}// 返回右下角位置的最小路径和（网格最后一行最后一列）returngrid[row-1][col-1];}}

注意：
初始化第一行时，i 的范围是小于列数！！！
初始化第一列时，i 的范围是小于行数！！！

3.例子

以下图为例

[ [1, 3, 1], [1, 5, 1], [4, 2, 1] ]

目标：从左上角(0,0)走到右下角(2,2)，只能向右/向下走，求路径和最小的值。

步骤1：初始化第一行（只能从左边走过来）
第一行原始：[1, 3, 1]

• grid[0][1] = 3 + grid[0][0] = 3 + 1 = 4
• grid[0][2] = 1 + grid[0][1] = 1 + 4 = 5

第一行更新为：[1, 4, 5]

步骤2：初始化第一列（只能从上面走下来）
第一列原始：[1, 1, 4]

• grid[1][0] = 1 + grid[0][0] = 1 + 1 = 2
• grid[2][0] = 4 + grid[1][0] = 4 + 2 = 6

第一列更新为：[1, 2, 6]

此时网格变为：

[ [1, 4, 5], [2, 5, 1], [6, 2, 1] ]

步骤3：遍历中间格子（取上方/左方的较小路径和）
① 位置(1,1)（值为 5）
grid[1][1] = 5 + min(上方 grid[0][1]=4, 左方 grid[1][0]=2)
= 5 + 2 = 7

网格更新为：

[ [1, 4, 5], [2, 7, 1], [6, 2, 1] ]

② 位置(1,2)（值为 1）
grid[1][2] = 1 + min(上方 grid[0][2]=5, 左方 grid[1][1]=7)
= 1 + 5 = 6

网格更新为：

[ [1, 4, 5], [2, 7, 6], [6, 2, 1] ]

③ 位置(2,1)（值为 2）
grid[2][1] = 2 + min(上方 grid[1][1]=7, 左方 grid[2][0]=6)
= 2 + 6 = 8

网格更新为：

[ [1, 4, 5], [2, 7, 6], [6, 8, 1] ]

④ 位置(2,2)（终点，值为 1）
grid[2][2] = 1 + min(上方 grid[1][2]=6, 左方 grid[2][1]=8)
= 1 + 6 = 7

最终结果
右下角grid[2][2] = 7
最小路径和为 7

对应一条最小路径：1 → 3 → 1 → 1 → 1（和为1+1+3+1+1=7）

三、最长回文子串

1.题目

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

示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：“bb”

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

2.代码

classSolution{publicStringlongestPalindrome(Strings){intresLen=0;// 记录最长回文子串的长度intresStart=0;// 记录最长回文子串的起始索引// 遍历每个字符，从字符为中心扩展（处理两种回文情况）for(inti=0;i<s.length();i++){// 情况1：回文长度为奇数（中心是单个字符，如"bab"）intleft=i;intright=i;// 向左右扩展，直到字符不相等或越界while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){// 更新最长回文子串的信息if(right-left+1>resLen){resLen=right-left+1;resStart=left;}left--;right++;}// 情况2：回文长度为偶数（中心是两个字符，如"baab"）left=i;right=i+1;// 向左右扩展，直到字符不相等或越界while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){// 更新最长回文子串的信息if(right-left+1>resLen){resLen=right-left+1;resStart=left;}left--;right++;}}// 截取并返回最长回文子串returns.substring(resStart,resStart+resLen);}}

注意分两种情况哦，奇和偶！！！

3.例子

例子：输入字符串s = "babad"
目标：找出最长回文子串（结果：bab或aba，长度 3）

i = 0（字符 ‘b’）

① 奇数扩展：left=0, right=0

• s[0] = s[0]→ 符合
• 长度1 > 0→ 更新：
  resLen=1，resStart=0
• 继续扩展：left=-1，停止

② 偶数扩展：left=0, right=1

• s[0] = b，s[1] = a→ 不相等，不进入循环

当前最长："b"，长度 1

i = 1（字符 ‘a’）

① 奇数扩展：left=1, right=1

• 长度 1，不更新
• 扩展：left=0, right=2
  s[0] = b，s[2] = b→ 相等！
• 长度3 > 1→ 更新：
  resLen=3，resStart=0
• 再扩展：left=-1，停止

② 偶数扩展：left=1, right=2

• s[1]=a，s[2]=b→ 不相等

当前最长："bab"，长度 3

i = 2（字符 ‘b’）

① 奇数扩展：left=2, right=2

• 长度 1，不更新
• 扩展：left=1, right=3
  s[1]=a，s[3]=a→ 相等！
• 长度3（等于当前最长）
  可更新可不更新，这里不变
• 再扩展：left=0, right=4 → 不相等

② 偶数扩展：left=2, right=3

• s[2]=b，s[3]=a→ 不相等

当前最长：仍为 3

i = 3（字符 ‘a’）

① 奇数扩展：left=3, right=3

• 长度 1，不更新
• 扩展：left=2, right=4 → 不相等

② 偶数扩展：left=3, right=4

• s[3]=a，s[4]=d→ 不相等

i = 4（字符 ‘d’）

① 奇数扩展：长度 1，不更新
② 偶数扩展：越界，不执行

最终结果

• resStart = 0
• resLen = 3
• 截取：s.substring(0, 0+3)→"bab"

最终答案：bab

四、最长公共子序列

1.题目

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
  两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：
输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。

示例 2：
输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc” ，它的长度为 3 。

示例 3：
输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

2.代码

classSolution{publicintlongestCommonSubsequence(Stringtext1,Stringtext2){// 获取两个字符串的长度intlen1=text1.length();intlen2=text2.length();// dp[i][j]：表示text1的前i个字符 和 text2的前j个字符的最长公共子序列长度// 初始化dp数组，行列都多开1个（方便处理i=0或j=0的边界情况，此时公共子序列长度为0）int[][]dp=newint[len1+1][len2+1];// 遍历text1的每个字符for(inti=0;i<len1;i++){// 遍历text2的每个字符for(intj=0;j<len2;j++){if(text1.charAt(i)==text2.charAt(j)){// 情况1：当前字符相等，公共子序列长度 = 前i-1和前j-1的长度 + 1dp[i+1][j+1]=dp[i][j]+1;}else{// 情况2：当前字符不相等，取“text1前i个+text2前j-1个”或“text1前i-1个+text2前j个”的较大值dp[i+1][j+1]=Math.max(dp[i+1][j],dp[i][j+1]);}}}// 最终结果：text1整个字符串和text2整个字符串的最长公共子序列长度returndp[len1][len2];}}

对应关系
字符串第 i 个字符 = dp 表格第 i + 1 行
因为 dp 表格第 0 行，专门用来表示 “空字符串”！

例：
字符串 text1 = “a b c”
索引：0 1 2

前 0 个字符 → 空 → dp [0][…]
前 1 个字符 → a → 对应索引 0
前 2 个字符 → a b → 对应索引 1
前 3 个字符 → a b c → 对应索引 2

3.例子

输入：text1 = “abcde”，text2 = “ace”
输出：3

第一步：明确变量

• text1 = "abcde"→ 长度len1 = 5
• text2 = "ace"→ 长度len2 = 3
• 创建dp 数组：new int[5+1][3+1]→dp[6][4]
• dp[i][j] 含义：text1 前 i 个字符 和 text2 前 j 个字符 的最长公共子序列长度

第二步：初始 dp 表格（全 0）
行：0~5（对应 text1：空、a、b、c、d、e）
列：0~3（对应 text2：空、a、c、e）

j=0 j=1 j=2 j=3 (空) a c e i=0 (空) [0, 0, 0, 0] i=1 a [0, ?, ?, ?] i=2 b [0, ?, ?, ?] i=3 c [0, ?, ?, ?] i=4 d [0, ?, ?, ?] i=5 e [0, ?, ?, ?]

#第三步：跟着代码循环计算
循环：
i遍历 text1：0(a), 1(b), 2©, 3(d), 4(e)
j遍历 text2：0(a), 1©, 2(e)

① i=0（text1[0] = ‘a’）

j=0（text2[0] = ‘a’）
字符相等
dp[1][1] = dp[0][0] + 1 = 0 + 1 = 1

j=1（text2[1] = ‘c’）
不等
dp[1][2] = max(dp[1][1], dp[0][2]) = max(1,0) = 1

j=2（text2[2] = ‘e’）
不等
dp[1][3] = max(dp[1][2], dp[0][3]) = max(1,0) = 1

第一行填完：

[0, 0, 0, 0] [0, 1, 1, 1]

② i=1（text1[1] = ‘b’）

j=0 → a：不等 → dp[2][1] = 1

j=1 → c：不等 → dp[2][2] = 1

j=2 → e：不等 → dp[2][3] = 1

第二行填完：

[0, 1, 1, 1] [0, 1, 1, 1]

③ i=2（text1[2] = ‘c’）

j=0 → a：不等 → dp[3][1] = 1

j=1 → c：相等！
dp[3][2] = dp[2][1] + 1 = 1 + 1 = 2

j=2 → e：不等 → dp[3][3] = max(2, 1) = 2

第三行填完：

[0, 1, 1, 1] [0, 1, 1, 1] [0, 1, 2, 2]

④ i=3（text1[3] = ‘d’）
全部不等，全部继承上面的值：
dp[4][1]=1
dp[4][2]=2
dp[4][3]=2

第四行填完：

[0, 1, 1, 1] [0, 1, 1, 1] [0, 1, 2, 2] [0, 1, 2, 2]

⑤ i=4（text1[4] = ‘e’）

j=0 → a：不等 → dp[5][1]=1

j=1 → c：不等 → dp[5][2]=2

j=2 → e：相等！
dp[5][3] = dp[4][2] + 1 = 2 + 1 = 3

最终 dp 表格

[0, 0, 0, 0] [0, 1, 1, 1] [0, 1, 1, 1] [0, 1, 2, 2] [0, 1, 2, 2] [0, 1, 2, 3]

• 最终答案：dp[5][3] = 3

五、 编辑距离

1.题目

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例 1：
输入：word1 = “horse”, word2 = “ros”
输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)

示例 2：
输入：word1 = “intention”, word2 = “execution”
输出：5
解释：
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)

提示：

• 0 <= word1.length, word2.length <= 500
• word1 和 word2 由小写英文字母组成

2.代码

classSolution{publicintminDistance(Stringword1,Stringword2){intlen1=word1.length();intlen2=word2.length();// 定义dp数组：dp[i][j]表示word1前i个字符 转成 word2前j个字符的最少操作数int[][]dp=newint[len1+1][len2+1];// 初始化：word1为空时，转成word2需要逐个插入（操作数=word2长度）for(inti=1;i<=len2;++i){dp[0][i]=dp[0][i-1]+1;}// 初始化：word2为空时，转成word2需要逐个删除（操作数=word1长度）for(inti=1;i<=len1;++i){dp[i][0]=dp[i-1][0]+1;}// 填充dp数组for(inti=1;i<=len1;++i){for(intj=1;j<=len2;++j){if(word1.charAt(i-1)==word2.charAt(j-1)){//// 字符相同，无需操作，继承之前的状态dp[i][j]=dp[i-1][j-1];}else{// 字符不同，取“替换、删除、插入”三种操作的最小值+1,即表格中上方，左方，左上方三个元素的最小值+1dp[i][j]=Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;}}}// dp[len1][len2]就是最终结果returndp[len1][len2];}}

定义dp数组：
dp[i][j]表示word1前i个字符 转成 word2前j个字符的最少操作数

① dp[i-1][j-1] → 替换操作

• 意思：word1 前 i-1 个 → word2 前 j-1 个
• 当前字符不同，直接替换 1 次就够了
• 所以 = 之前的结果 + 1 次替换

② dp[i-1][j] → 删除操作

• 意思：word1 前 i-1 个 → 已经变成 word2 前 j 个
• 那我把 word1 第 i 个字符删掉 就行
• 所以 = 这个结果 + 1 次删除

③ dp[i][j-1] → 插入操作

• 意思：word1 前 i 个 → 已经变成 word2 前 j-1 个
• 那我 给 word1 插入一个字符 匹配 word2 第 j 个
• 所以 = 这个结果 + 1 次插入

3.例子

输入：word1 = "intention"，word2 = "execution"
输出：5

关键：

1. 字符一样→ 直接用左上角的值
2. 字符不一样→ 取左上、上边、左边最小的数+1

1. 创建 dp 表

• intention长度 = 9
• execution长度 = 9
• 代码创建：10 行 × 10 列的表（多一行一列放空字符串）

2. 初始化第一行 & 第一列

• 第一行：空 → execution →[0,1,2,3,4,5,6,7,8,9]
• 第一列：intention → 空 →[0,1,2,3,4,5,6,7,8,9]

3. 逐行填表

两个单词对齐

word1：i n t e n t i o n （9个字母） word2：e x e c u t i o n （9个字母）

① 前 5 个字母：全都不一样
每对比到不同的字母，代码都会：
取最小 +1
所以前 5 步，每一步都+1

② 从第 6 个字母开始：全都一样！

t == t i == i o == o n == n

字符一样 → 直接继承左上角的值，不再增加步数！

4. 返回右下角的值
表格最后一格dp[9][9]=5

总结

1. 建表 → 初始化第一行/列
2. 对比字母：
   • 不一样 → 操作数 +1
   • 一样 → 不增加
3. 前 5 个字母不同 → 累计 5
4. 后 4 个字母相同 → 不增加
5. 最终结果 =5

最终答案
return dp[9][9] = 5

如果本篇文章对您有帮助，可以点赞，收藏或评论哦！！！关注主包不迷路，让我们一起向前进步吧！！