前言在力扣Hot100算法题中动态规划是占比最高、面试最常考的模块而多维动态规划二维DP为主是DP的进阶核心。区别于一维DP仅依赖单一线性状态多维DP需要同时维护两个及以上维度的状态适配矩阵路径、双字符串匹配、区间最值等复杂场景。很多同学刷题只会背DP公式遇到变式题就无从下手核心原因是跳过了暴力枚举→记忆化搜索→迭代DP的思维演进过程。本文将固定一套通用解题逻辑拆解Hot100中所有高频多维DP真题帮大家彻底吃透多维DP底层逻辑做到以不变应万变。一、多维DP通用解题模板所有题目通用核心思路三步走思维演进1. 暴力递归找到问题本质不考虑时间复杂度纯暴力枚举所有可能情况拆解问题的子问题拆分规则、状态转移关系和递归终止条件。暴力递归的核心意义是帮我们理清题目所有决策分支是后续优化的基础。2. 记忆化搜索优化重复子问题暴力递归的致命缺陷是大量重叠子问题被重复计算时间复杂度极高。我们新增一个多维缓存数组存储已经计算过的子问题结果下次遇到相同状态直接复用结果避免重复递归大幅降低时间复杂度。3. 迭代动态规划最终最优解法将自上而下的记忆化递归转化为自下而上的多维数组迭代推导。手动控制遍历顺序、初始化边界状态去掉递归栈开销实现时间、空间最优解也是面试、刷题的标准写法。多维DP适用场景问题需要同时满足两个维度的状态约束常见场景矩阵网格路径问题、两个字符串比对问题、区间子串最值问题。二、Hot100 多维DP真题逐题精讲题162. 不同路径题目描述一个机器人位于一个m x n网格的左上角 起始点在下图中标记为 “Start” 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。问总共有多少条不同的路径示例 1输入m 3, n 7输出28核心思路暴力→记忆化→多维DP1. 暴力递归思路子问题拆分到达坐标 (i,j) 的路径数 到达上方 (i-1,j) 的路径数 到达左方 (i,j-1) 的路径数。因为机器人只能向下、向右走当前位置的所有路径都来自上、左两个方向。递归终止条件当 i0 或 j0 时处于网格第一行或第一列只有一条路径一直向右/一直向下直接返回1。暴力缺陷存在海量重叠子问题例如网格中间位置的坐标会被多次递归计算网格越大重复计算次数越多时间复杂度指数级爆炸。2. 记忆化搜索优化定义二维缓存数组memo[i][j]存储到达 (i,j) 的路径数。每次递归前先判断缓存是否存在结果存在则直接返回不存在则计算后存入缓存。优化效果彻底消除重叠子问题每个坐标状态仅计算一次时间复杂度从 O(2^(mn)) 降至 O(m*n)。3. 二维迭代DP最终解法状态定义dp[i][j]表示从起点到达 (i,j) 的不同路径数。状态转移方程dp[i][j] dp[i-1][j] dp[i][j-1]初始化第一行、第一列所有位置初始化为1边界位置无其他路径可选。遍历顺序从上到下、从左到右逐行遍历保证计算当前状态时上、左前置状态已计算完成。代码实现// 62. 不同路径 // 动态规划二维DP 自下而上迭代 class Solution { public: int uniquePaths(int m, int n) { // dp[i][j]从(0,0)走到(i,j)的路径总数 vectorvectorint dp(m, vectorint(n, 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]; } };题264. 最小路径和题目描述给定一个包含非负整数的mxn网格grid请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。说明每次只能向下或者向右移动一步。示例 1输入grid [[1,3,1],[1,5,1],[4,2,1]]输出7解释因为路径 1→3→1→1→1 的总和最小。核心思路暴力→记忆化→多维DP思考提问对比不同路径本题的状态转移有什么区别边界初始化需要特殊处理吗1. 暴力递归思路子问题拆分到达 (i,j) 的最小路径和 当前网格值 min(上方位置最小路径和, 左方位置最小路径和)。递归终止条件起点 (0,0) 直接返回网格原值第一行位置只能从左转移第一列位置只能从上转移。暴力缺陷同样存在大量重叠子问题重复计算每个坐标的最小路径和大数据量下超时严重。2. 记忆化搜索优化定义二维缓存数组memo[i][j]存储 (i,j) 位置的最小路径和缓存已计算的子问题结果避免重复递归时间复杂度优化至 O(m*n)。3. 二维迭代DP最终解法状态定义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]单独初始化第一行、第一列的累加和。遍历顺序从上到下、从左到右保证前置状态优先计算。代码实现// 64. 最小路径和 // 二维DP每次只能从上/左转移取最小值 class Solution { public: int minPathSum(vectorvectorint grid) { int m grid.size(); int n grid[0].size(); // dp[i][j]走到(i,j)的最小路径和 vectorvectorint dp(m, vectorint(n, 0)); // 初始化起点 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]; } // 遍历其余位置 for (int i 1; i m; i) { for (int j 1; j n; j) { // 当前值 上方/左方最小路径 dp[i][j] grid[i][j] min(dp[i - 1][j], dp[i][j - 1]); } } return dp[m - 1][n - 1]; } };题35. 最长回文子串题目描述给你一个字符串s找到s中最长的 回文 子串。示例 1输入s babad输出bab解释aba 同样是符合题意的答案。核心思路暴力→记忆化→多维DP思考提问回文串的状态为什么需要二维数组区间DP的遍历顺序和普通网格DP有什么不同1. 暴力递归思路子问题拆分判断子串 s[i...j] 是否为回文串等价于首尾字符相等 中间子串 s[i1...j-1] 是回文串。递归终止条件i j 时单个字符一定是回文串j i1 时两个字符相等即为回文串。暴力缺陷暴力枚举所有子串逐个判断回文时间复杂度 O(n³)超长字符串直接超时且大量区间子问题重复判断。2. 记忆化搜索优化定义二维缓存memo[i][j]记录区间 [i,j] 是否为回文串缓存判断结果避免重复校验同一区间消除重复子问题。3. 二维区间DP最终解法状态定义dp[i][j]表示字符串区间 [i,j] 是否为回文串布尔值。状态转移方程dp[i][j] (s[i]s[j]) and dp[i1][j-1]初始化所有长度为1的子串dp[i][i] True。遍历顺序按子串长度从小到大遍历区间DP核心短区间结果推导长区间结果全程记录最长回文子串。代码实现// 5. 最长回文子串 // 区间DPdp[i][j] 表示区间 [i,j] 是否为回文串 class Solution { public: string longestPalindrome(string s) { int n s.size(); if (n 2) return s; // 二维布尔dp数组记录区间回文状态 vectorvectorbool dp(n, vectorbool(n, false)); int maxLen 1; // 最长回文长度 int start 0; // 最长回文起始下标 // 初始化单个字符一定是回文 for (int i 0; i n; i) { dp[i][i] true; } // 按子串长度从小到大遍历区间DP核心 for (int len 2; len n; len) { // i为起点j为终点 for (int i 0; i len - 1 n; i) { int j i len - 1; if (s[i] s[j]) { // 长度为2直接判定长度大于2依赖子区间 if (len 2) { dp[i][j] true; } else { dp[i][j] dp[i 1][j - 1]; } } // 更新最长回文子串 if (dp[i][j] len maxLen) { maxLen len; start i; } } } return s.substr(start, maxLen); } };题41143. 最长公共子序列题目描述给定两个字符串text1和text2返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列返回0。一个字符串的子序列是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。例如ace是abcde的子序列但aec不是abcde的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。示例 1输入text1 abcde, text2 ace输出3解释最长公共子序列是 ace 它的长度为 3 。核心思路暴力→记忆化→多维DP1. 暴力递归思路子问题拆分对比两个字符串末尾字符若相等公共子序列长度1同时前移两个指针若不相等分别前移其中一个指针取最大值。递归终止条件任意字符串指针遍历完毕返回0。暴力缺陷双指针组合状态海量重叠子问题极多时间复杂度指数级完全无法通过大数据用例。2. 记忆化搜索优化定义二维缓存memo[i][j]存储 text1前i个字符、text2前j个字符的最长公共子序列长度缓存所有状态结果时间复杂度降至 O(m*n)。3. 二维迭代DP最终解法状态定义dp[i][j]表示 text1前i个字符、text2前j个字符的最长公共子序列长度。状态转移方程1. 若 text1[i-1] text2[j-1]dp[i][j] dp[i-1][j-1] 12. 若不相等dp[i][j] max(dp[i-1][j], dp[i][j-1])初始化dp数组第0行、第0列全部为0空字符串无公共子序列。遍历顺序逐行逐列遍历保证前置子状态计算完成。代码实现// 1143. 最长公共子序列 LCS // 二维DP解决双字符串匹配问题 class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m text1.size(); int n text2.size(); // dp[i][j]text1前i个字符、text2前j个字符的LCS长度 vectorvectorint dp(m 1, vectorint(n 1, 0)); for (int i 1; i m; i) { for (int j 1; j n; j) { // 字符相等当前LCS 前一层LCS 1 if (text1[i - 1] text2[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; } // 字符不等取上方或左方最大值 else { dp[i][j] max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } };题572. 编辑距离题目描述给你两个单词word1和word2请返回将word1转换成word2所使用的最少操作数。你可以对一个单词进行如下三种操作插入一个字符删除一个字符替换一个字符示例 1输入word1 horse, word2 ros输出3解释horse - rorse (将 h 替换为 r) rorse - rose (删除 r) rose - ros (删除 e)核心思路暴力→记忆化→多维DP思考提问三种操作如何对应DP状态转移1. 暴力递归思路子问题拆分对比两字符串末尾字符相等则无需操作直接前移双指针i-1j-1不相等时我们有三种可选操作每一种操作都可以映射到递归指针的变化删除 word1 的末尾字符删掉 word1 [i‑1]相当于 word1 指针向前走一步i-1j 不变在 word1 末尾插入一个字符匹配 word2 的末尾插入字符等价于把 word2 的末尾消耗掉word2 指针向前走一步j‑1i 不变替换 word1 的末尾字符为 word2 的末尾字符替换完成后两个末尾字符匹配两个指针同时向前i‑1j‑1。递归终止条件其中一个字符串遍历完毕剩余字符全部删除/插入操作数等于剩余字符长度。暴力缺陷三分支递归叠加重叠子问题数量爆炸时间复杂度极高无法落地。2. 记忆化搜索优化定义二维缓存memo[i][j]存储 word1前i字符转word2前j字符的最少操作数缓存所有子问题结果剔除重复计算。3. 二维迭代DP最终解法状态定义dp[i][j]表示 word1前i个字符转换为 word2前j个字符的最少编辑操作数。状态转移方程1. 字符相等dp[i][j] dp[i-1][j-1]2. 字符不等dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1删除、插入、替换初始化dp[i][0] i全部删除dp[0][j] j全部插入。遍历顺序自上而下、自左而右迭代推导。代码实现// 72. 编辑距离 // 二维DP插入、删除、替换三种操作取最小 class Solution { public: int minDistance(string word1, string word2) { int m word1.size(); int n word2.size(); // dp[i][j]word1前i个字符转为word2前j个字符的最小操作数 vectorvectorint dp(m 1, vectorint(n 1, 0)); // 边界初始化 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[i - 1] word2[j - 1]) { dp[i][j] dp[i - 1][j - 1]; } // 字符不等删除/插入/替换 取最小1 else { dp[i][j] min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) 1; } } } return dp[m][n]; } };
前言在力扣Hot100算法题中动态规划是占比最高、面试最常考的模块而多维动态规划二维DP为主是DP的进阶核心。区别于一维DP仅依赖单一线性状态多维DP需要同时维护两个及以上维度的状态适配矩阵路径、双字符串匹配、区间最值等复杂场景。很多同学刷题只会背DP公式遇到变式题就无从下手核心原因是跳过了暴力枚举→记忆化搜索→迭代DP的思维演进过程。本文将固定一套通用解题逻辑拆解Hot100中所有高频多维DP真题帮大家彻底吃透多维DP底层逻辑做到以不变应万变。一、多维DP通用解题模板所有题目通用核心思路三步走思维演进1. 暴力递归找到问题本质不考虑时间复杂度纯暴力枚举所有可能情况拆解问题的子问题拆分规则、状态转移关系和递归终止条件。暴力递归的核心意义是帮我们理清题目所有决策分支是后续优化的基础。2. 记忆化搜索优化重复子问题暴力递归的致命缺陷是大量重叠子问题被重复计算时间复杂度极高。我们新增一个多维缓存数组存储已经计算过的子问题结果下次遇到相同状态直接复用结果避免重复递归大幅降低时间复杂度。3. 迭代动态规划最终最优解法将自上而下的记忆化递归转化为自下而上的多维数组迭代推导。手动控制遍历顺序、初始化边界状态去掉递归栈开销实现时间、空间最优解也是面试、刷题的标准写法。多维DP适用场景问题需要同时满足两个维度的状态约束常见场景矩阵网格路径问题、两个字符串比对问题、区间子串最值问题。二、Hot100 多维DP真题逐题精讲题162. 不同路径题目描述一个机器人位于一个m x n网格的左上角 起始点在下图中标记为 “Start” 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。问总共有多少条不同的路径示例 1输入m 3, n 7输出28核心思路暴力→记忆化→多维DP1. 暴力递归思路子问题拆分到达坐标 (i,j) 的路径数 到达上方 (i-1,j) 的路径数 到达左方 (i,j-1) 的路径数。因为机器人只能向下、向右走当前位置的所有路径都来自上、左两个方向。递归终止条件当 i0 或 j0 时处于网格第一行或第一列只有一条路径一直向右/一直向下直接返回1。暴力缺陷存在海量重叠子问题例如网格中间位置的坐标会被多次递归计算网格越大重复计算次数越多时间复杂度指数级爆炸。2. 记忆化搜索优化定义二维缓存数组memo[i][j]存储到达 (i,j) 的路径数。每次递归前先判断缓存是否存在结果存在则直接返回不存在则计算后存入缓存。优化效果彻底消除重叠子问题每个坐标状态仅计算一次时间复杂度从 O(2^(mn)) 降至 O(m*n)。3. 二维迭代DP最终解法状态定义dp[i][j]表示从起点到达 (i,j) 的不同路径数。状态转移方程dp[i][j] dp[i-1][j] dp[i][j-1]初始化第一行、第一列所有位置初始化为1边界位置无其他路径可选。遍历顺序从上到下、从左到右逐行遍历保证计算当前状态时上、左前置状态已计算完成。代码实现// 62. 不同路径 // 动态规划二维DP 自下而上迭代 class Solution { public: int uniquePaths(int m, int n) { // dp[i][j]从(0,0)走到(i,j)的路径总数 vectorvectorint dp(m, vectorint(n, 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]; } };题264. 最小路径和题目描述给定一个包含非负整数的mxn网格grid请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。说明每次只能向下或者向右移动一步。示例 1输入grid [[1,3,1],[1,5,1],[4,2,1]]输出7解释因为路径 1→3→1→1→1 的总和最小。核心思路暴力→记忆化→多维DP思考提问对比不同路径本题的状态转移有什么区别边界初始化需要特殊处理吗1. 暴力递归思路子问题拆分到达 (i,j) 的最小路径和 当前网格值 min(上方位置最小路径和, 左方位置最小路径和)。递归终止条件起点 (0,0) 直接返回网格原值第一行位置只能从左转移第一列位置只能从上转移。暴力缺陷同样存在大量重叠子问题重复计算每个坐标的最小路径和大数据量下超时严重。2. 记忆化搜索优化定义二维缓存数组memo[i][j]存储 (i,j) 位置的最小路径和缓存已计算的子问题结果避免重复递归时间复杂度优化至 O(m*n)。3. 二维迭代DP最终解法状态定义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]单独初始化第一行、第一列的累加和。遍历顺序从上到下、从左到右保证前置状态优先计算。代码实现// 64. 最小路径和 // 二维DP每次只能从上/左转移取最小值 class Solution { public: int minPathSum(vectorvectorint grid) { int m grid.size(); int n grid[0].size(); // dp[i][j]走到(i,j)的最小路径和 vectorvectorint dp(m, vectorint(n, 0)); // 初始化起点 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]; } // 遍历其余位置 for (int i 1; i m; i) { for (int j 1; j n; j) { // 当前值 上方/左方最小路径 dp[i][j] grid[i][j] min(dp[i - 1][j], dp[i][j - 1]); } } return dp[m - 1][n - 1]; } };题35. 最长回文子串题目描述给你一个字符串s找到s中最长的 回文 子串。示例 1输入s babad输出bab解释aba 同样是符合题意的答案。核心思路暴力→记忆化→多维DP思考提问回文串的状态为什么需要二维数组区间DP的遍历顺序和普通网格DP有什么不同1. 暴力递归思路子问题拆分判断子串 s[i...j] 是否为回文串等价于首尾字符相等 中间子串 s[i1...j-1] 是回文串。递归终止条件i j 时单个字符一定是回文串j i1 时两个字符相等即为回文串。暴力缺陷暴力枚举所有子串逐个判断回文时间复杂度 O(n³)超长字符串直接超时且大量区间子问题重复判断。2. 记忆化搜索优化定义二维缓存memo[i][j]记录区间 [i,j] 是否为回文串缓存判断结果避免重复校验同一区间消除重复子问题。3. 二维区间DP最终解法状态定义dp[i][j]表示字符串区间 [i,j] 是否为回文串布尔值。状态转移方程dp[i][j] (s[i]s[j]) and dp[i1][j-1]初始化所有长度为1的子串dp[i][i] True。遍历顺序按子串长度从小到大遍历区间DP核心短区间结果推导长区间结果全程记录最长回文子串。代码实现// 5. 最长回文子串 // 区间DPdp[i][j] 表示区间 [i,j] 是否为回文串 class Solution { public: string longestPalindrome(string s) { int n s.size(); if (n 2) return s; // 二维布尔dp数组记录区间回文状态 vectorvectorbool dp(n, vectorbool(n, false)); int maxLen 1; // 最长回文长度 int start 0; // 最长回文起始下标 // 初始化单个字符一定是回文 for (int i 0; i n; i) { dp[i][i] true; } // 按子串长度从小到大遍历区间DP核心 for (int len 2; len n; len) { // i为起点j为终点 for (int i 0; i len - 1 n; i) { int j i len - 1; if (s[i] s[j]) { // 长度为2直接判定长度大于2依赖子区间 if (len 2) { dp[i][j] true; } else { dp[i][j] dp[i 1][j - 1]; } } // 更新最长回文子串 if (dp[i][j] len maxLen) { maxLen len; start i; } } } return s.substr(start, maxLen); } };题41143. 最长公共子序列题目描述给定两个字符串text1和text2返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列返回0。一个字符串的子序列是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。例如ace是abcde的子序列但aec不是abcde的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。示例 1输入text1 abcde, text2 ace输出3解释最长公共子序列是 ace 它的长度为 3 。核心思路暴力→记忆化→多维DP1. 暴力递归思路子问题拆分对比两个字符串末尾字符若相等公共子序列长度1同时前移两个指针若不相等分别前移其中一个指针取最大值。递归终止条件任意字符串指针遍历完毕返回0。暴力缺陷双指针组合状态海量重叠子问题极多时间复杂度指数级完全无法通过大数据用例。2. 记忆化搜索优化定义二维缓存memo[i][j]存储 text1前i个字符、text2前j个字符的最长公共子序列长度缓存所有状态结果时间复杂度降至 O(m*n)。3. 二维迭代DP最终解法状态定义dp[i][j]表示 text1前i个字符、text2前j个字符的最长公共子序列长度。状态转移方程1. 若 text1[i-1] text2[j-1]dp[i][j] dp[i-1][j-1] 12. 若不相等dp[i][j] max(dp[i-1][j], dp[i][j-1])初始化dp数组第0行、第0列全部为0空字符串无公共子序列。遍历顺序逐行逐列遍历保证前置子状态计算完成。代码实现// 1143. 最长公共子序列 LCS // 二维DP解决双字符串匹配问题 class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m text1.size(); int n text2.size(); // dp[i][j]text1前i个字符、text2前j个字符的LCS长度 vectorvectorint dp(m 1, vectorint(n 1, 0)); for (int i 1; i m; i) { for (int j 1; j n; j) { // 字符相等当前LCS 前一层LCS 1 if (text1[i - 1] text2[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; } // 字符不等取上方或左方最大值 else { dp[i][j] max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } };题572. 编辑距离题目描述给你两个单词word1和word2请返回将word1转换成word2所使用的最少操作数。你可以对一个单词进行如下三种操作插入一个字符删除一个字符替换一个字符示例 1输入word1 horse, word2 ros输出3解释horse - rorse (将 h 替换为 r) rorse - rose (删除 r) rose - ros (删除 e)核心思路暴力→记忆化→多维DP思考提问三种操作如何对应DP状态转移1. 暴力递归思路子问题拆分对比两字符串末尾字符相等则无需操作直接前移双指针i-1j-1不相等时我们有三种可选操作每一种操作都可以映射到递归指针的变化删除 word1 的末尾字符删掉 word1 [i‑1]相当于 word1 指针向前走一步i-1j 不变在 word1 末尾插入一个字符匹配 word2 的末尾插入字符等价于把 word2 的末尾消耗掉word2 指针向前走一步j‑1i 不变替换 word1 的末尾字符为 word2 的末尾字符替换完成后两个末尾字符匹配两个指针同时向前i‑1j‑1。递归终止条件其中一个字符串遍历完毕剩余字符全部删除/插入操作数等于剩余字符长度。暴力缺陷三分支递归叠加重叠子问题数量爆炸时间复杂度极高无法落地。2. 记忆化搜索优化定义二维缓存memo[i][j]存储 word1前i字符转word2前j字符的最少操作数缓存所有子问题结果剔除重复计算。3. 二维迭代DP最终解法状态定义dp[i][j]表示 word1前i个字符转换为 word2前j个字符的最少编辑操作数。状态转移方程1. 字符相等dp[i][j] dp[i-1][j-1]2. 字符不等dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1删除、插入、替换初始化dp[i][0] i全部删除dp[0][j] j全部插入。遍历顺序自上而下、自左而右迭代推导。代码实现// 72. 编辑距离 // 二维DP插入、删除、替换三种操作取最小 class Solution { public: int minDistance(string word1, string word2) { int m word1.size(); int n word2.size(); // dp[i][j]word1前i个字符转为word2前j个字符的最小操作数 vectorvectorint dp(m 1, vectorint(n 1, 0)); // 边界初始化 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[i - 1] word2[j - 1]) { dp[i][j] dp[i - 1][j - 1]; } // 字符不等删除/插入/替换 取最小1 else { dp[i][j] min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) 1; } } } return dp[m][n]; } };
