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

文章目录前言一、不同路径1.题目2.代码3.例子二、最小路径和1.题目2.代码3.例子三、最长回文子串1.题目2.代码3.例子四、最长公共子序列1.题目2.代码3.例子五、 编辑距离1.题目2.代码3.例子前言本文记录力扣Hot100里面关于多维动态规划的五道题包括常见解法和一些关键步骤理解也有例子便于大家理解一、不同路径1.题目一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。问总共有多少条不同的路径示例 1输入m 3, n 7输出28示例 2输入m 3, n 2输出3解释从左上角开始总共有 3 条路径可以到达右下角。向右 - 向下 - 向下向下 - 向下 - 向右向下 - 向右 - 向下示例 3输入m 7, n 3输出28示例 4输入m 3, n 3输出62.代码classSolution{publicintuniquePaths(intm,intn){// f[i][j]从左上角(0,0)走到(i,j)的不同路径数int[][]fnewint[m][n];// 初始化第一列所有(i,0)位置只能向下走到达路径数为1for(inti0;im;i){f[i][0]1;}// 初始化第一行所有(0,j)位置只能向右走到达路径数为1for(intj0;jn;j){f[0][j]1;}// 递推计算每个位置的路径数从第二行第二列开始for(inti1;im;i){for(intj1;jn;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.例子以m4、n3为例前提数组f[i][j]从左上角(0,0)走到(i,j)的不同路径数仅能向右/向下走第一行/第一列因单方向可达路径数全为1其余位置路径数上方f[i-1][j]左方f[i][j-1]。步骤1初始化4行3列数组f定义f[4][3]行03、列02初始所有值为0。步骤2初始化第一列所有i,0列固定为0行遍历0~3仅能从上方连续向下走到达所有位置路径数赋值为1f[0][0]1、f[1][0]1、f[2][0]1、f[3][0]1。步骤3初始化第一行所有0,j行固定为0列遍历0~2仅能从左方连续向右走到达所有位置路径数赋值为1f[0][0]1已赋值、f[0][1]1、f[0][2]1。步骤4递推计算所有非第一行/第一列的位置i从1到3j从1到2第一轮i1第二行j依次取1、2j1f[1][1] f[0][1]上方 f[1][0]左方 112j2f[1][2] f[0][2]上方 f[1][1]左方 123第二轮i2第三行j依次取1、2j1f[2][1] f[1][1]上方 f[2][0]左方 213j2f[2][2] f[1][2]上方 f[2][1]左方 336第三轮i3第四行最后一行j依次取1、2j1f[3][1] f[2][1]上方 f[3][0]左方 314j2f[3][2] f[2][2]上方 f[3][1]左方 6410步骤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]]输出122.代码classSolution{publicintminPathSum(int[][]grid){// 获取网格的行数和列数introwgrid.length;//行intcolgrid[0].length;//列// 初始化第一行第一行只能从左边走过来路径和累加左边的值for(inti1;icol;i){grid[0][i]grid[0][i-1];}// 初始化第一列第一列只能从上面走下来路径和累加上面的值for(inti1;irow;i){grid[i][0]grid[i-1][0];}// 遍历网格的其他位置从第二行第二列开始for(inti1;irow;i){for(intj1;jcol;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 4grid[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 2grid[2][0] 4 grid[1][0] 4 2 6第一列更新为[1, 2, 6]此时网格变为[ [1, 4, 5], [2, 5, 1], [6, 2, 1] ]步骤3遍历中间格子取上方/左方的较小路径和① 位置(1,1)值为 5grid[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)值为 1grid[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)值为 2grid[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)终点值为 1grid[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和为113117三、最长回文子串1.题目给你一个字符串 s找到 s 中最长的 回文 子串。示例 1输入s “babad”输出“bab”解释“aba” 同样是符合题意的答案。示例 2输入s “cbbd”输出“bb”提示1 s.length 1000s 仅由数字和英文字母组成2.代码classSolution{publicStringlongestPalindrome(Strings){intresLen0;// 记录最长回文子串的长度intresStart0;// 记录最长回文子串的起始索引// 遍历每个字符从字符为中心扩展处理两种回文情况for(inti0;is.length();i){// 情况1回文长度为奇数中心是单个字符如babintlefti;intrighti;// 向左右扩展直到字符不相等或越界while(left0rights.length()s.charAt(left)s.charAt(right)){// 更新最长回文子串的信息if(right-left1resLen){resLenright-left1;resStartleft;}left--;right;}// 情况2回文长度为偶数中心是两个字符如baablefti;righti1;// 向左右扩展直到字符不相等或越界while(left0rights.length()s.charAt(left)s.charAt(right)){// 更新最长回文子串的信息if(right-left1resLen){resLenright-left1;resStartleft;}left--;right;}}// 截取并返回最长回文子串returns.substring(resStart,resStartresLen);}}注意分两种情况哦奇和偶3.例子例子输入字符串s babad目标找出最长回文子串结果bab或aba长度 3i 0字符 ‘b’① 奇数扩展left0, right0s[0] s[0]→ 符合长度1 0→ 更新resLen1resStart0继续扩展left-1停止② 偶数扩展left0, right1s[0] bs[1] a→ 不相等不进入循环当前最长b长度 1i 1字符 ‘a’① 奇数扩展left1, right1长度 1不更新扩展left0, right2s[0] bs[2] b→ 相等长度3 1→ 更新resLen3resStart0再扩展left-1停止② 偶数扩展left1, right2s[1]as[2]b→ 不相等当前最长bab长度 3i 2字符 ‘b’① 奇数扩展left2, right2长度 1不更新扩展left1, right3s[1]as[3]a→ 相等长度3等于当前最长可更新可不更新这里不变再扩展left0, right4 → 不相等② 偶数扩展left2, right3s[2]bs[3]a→ 不相等当前最长仍为 3i 3字符 ‘a’① 奇数扩展left3, right3长度 1不更新扩展left2, right4 → 不相等② 偶数扩展left3, right4s[3]as[4]d→ 不相等i 4字符 ‘d’① 奇数扩展长度 1不更新② 偶数扩展越界不执行最终结果resStart 0resLen 3截取s.substring(0, 03)→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 1000text1 和 text2 仅由小写英文字符组成。2.代码classSolution{publicintlongestCommonSubsequence(Stringtext1,Stringtext2){// 获取两个字符串的长度intlen1text1.length();intlen2text2.length();// dp[i][j]表示text1的前i个字符 和 text2的前j个字符的最长公共子序列长度// 初始化dp数组行列都多开1个方便处理i0或j0的边界情况此时公共子序列长度为0int[][]dpnewint[len11][len21];// 遍历text1的每个字符for(inti0;ilen1;i){// 遍历text2的每个字符for(intj0;jlen2;j){if(text1.charAt(i)text2.charAt(j)){// 情况1当前字符相等公共子序列长度 前i-1和前j-1的长度 1dp[i1][j1]dp[i][j]1;}else{// 情况2当前字符不相等取“text1前i个text2前j-1个”或“text1前i-1个text2前j个”的较大值dp[i1][j1]Math.max(dp[i1][j],dp[i][j1]);}}}// 最终结果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 → 对应索引 23.例子输入text1 “abcde”text2 “ace”输出3第一步明确变量text1 abcde→ 长度len1 5text2 ace→ 长度len2 3创建dp 数组new int[51][31]→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、ej0 j1 j2 j3 (空) a c e i0 (空) [0, 0, 0, 0] i1 a [0, ?, ?, ?] i2 b [0, ?, ?, ?] i3 c [0, ?, ?, ?] i4 d [0, ?, ?, ?] i5 e [0, ?, ?, ?]#第三步跟着代码循环计算循环i遍历 text10(a), 1(b), 2©, 3(d), 4(e)j遍历 text20(a), 1©, 2(e)① i0text1[0] ‘a’j0text2[0] ‘a’字符相等dp[1][1] dp[0][0] 1 0 1 1j1text2[1] ‘c’不等dp[1][2] max(dp[1][1], dp[0][2]) max(1,0) 1j2text2[2] ‘e’不等dp[1][3] max(dp[1][2], dp[0][3]) max(1,0) 1第一行填完[0, 0, 0, 0] [0, 1, 1, 1]② i1text1[1] ‘b’j0 → a不等 → dp[2][1] 1j1 → c不等 → dp[2][2] 1j2 → e不等 → dp[2][3] 1第二行填完[0, 1, 1, 1] [0, 1, 1, 1]③ i2text1[2] ‘c’j0 → a不等 → dp[3][1] 1j1 → c相等dp[3][2] dp[2][1] 1 1 1 2j2 → e不等 → dp[3][3] max(2, 1) 2第三行填完[0, 1, 1, 1] [0, 1, 1, 1] [0, 1, 2, 2]④ i3text1[3] ‘d’全部不等全部继承上面的值dp[4][1]1dp[4][2]2dp[4][3]2第四行填完[0, 1, 1, 1] [0, 1, 1, 1] [0, 1, 2, 2] [0, 1, 2, 2]⑤ i4text1[4] ‘e’j0 → a不等 → dp[5][1]1j1 → c不等 → dp[5][2]2j2 → 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 500word1 和 word2 由小写英文字母组成2.代码classSolution{publicintminDistance(Stringword1,Stringword2){intlen1word1.length();intlen2word2.length();// 定义dp数组dp[i][j]表示word1前i个字符 转成 word2前j个字符的最少操作数int[][]dpnewint[len11][len21];// 初始化word1为空时转成word2需要逐个插入操作数word2长度for(inti1;ilen2;i){dp[0][i]dp[0][i-1]1;}// 初始化word2为空时转成word2需要逐个删除操作数word1长度for(inti1;ilen1;i){dp[i][0]dp[i-1][0]1;}// 填充dp数组for(inti1;ilen1;i){for(intj1;jlen2;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 intentionword2 execution输出5关键字符一样→ 直接用左上角的值字符不一样→ 取左上、上边、左边最小的数11. 创建 dp 表intention长度 9execution长度 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. 逐行填表两个单词对齐word1i n t e n t i o n 9个字母 word2e 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一样 → 不增加前 5 个字母不同 → 累计 5后 4 个字母相同 → 不增加最终结果 5最终答案return dp[9][9] 5如果本篇文章对您有帮助可以点赞收藏或评论哦关注主包不迷路让我们一起向前进步吧