langShift多维动态规划（题单顺序）
热题 100 - 多维动态规划分组（按题单顺序）：62 / 64 / 5 / 1143 / 72
本页包含题单「多维动态规划」分组的全部题目，顺序与 list.json 保持一致。
多维 DP 统一“落地步骤”（点击展开）
- 状态：
dp[i][j]表示什么（一定要带上“含义 + 范围”）。 - 转移：
dp[i][j]从哪些更小状态来，为什么不会漏/重。 - 初始化：边界（第一行/第一列/空串/长度为 0）怎么设，避免越界。
- 遍历顺序：保证用到的状态已经算好（常见是从小到大）。
- 优化：能否滚动数组（把二维压成一维），以及滚动时更新方向是否会污染数据。
62. 不同路径
一个机器人位于一个 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
提示：
1 <= m, n <= 100- 题目数据保证答案小于等于
2 * 109
最优解（二维 DP：dp[i][j]=dp[i-1][j]+dp[i][j-1]，可滚动成一维）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 题意：你站在左上角，每次只能往右或往下走一步，问到右下角一共有多少种不同的走法？
- 核心想法：走到某一个格子时，你只能从它的上面一格下来，或者从它的左边一格过来，没有别的路。所以「到达这个格子的走法数」=「到达上面那格的走法数」+「到达左边那格的走法数」。写成式子就是：
dp[i][j] = dp[i-1][j] + dp[i][j-1]。 - 边界：第一行只能一直往右走，第一列只能一直往下走，所以第一行、第一列每个格子都只有 1 种走法，初始化为 1。
- 空间优化：算每一行时只用得到「上一行」的结果，所以可以用一维数组「滚动」：
dp[j]表示当前行第 j 列有多少种走法，更新时用「上一行的 dp[j]」加上「当前行左边的 dp[j-1]」，即dp[j] = dp[j] + dp[j-1]。
类似题目（网格 DP：来自上/左）
思路相同：当前格子的值只依赖「上面」和「左边」，转移时用一维滚动即可，例如：
dp[j] = dp[j] + dp[j-1]
64. 最小路径和
给定一个包含非负整数的 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
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200
最优解（二维 DP：dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 和 62 一样，只是把“路径条数”换成“路径代价最小”。
- 到
grid[i][j]的最小代价只能来自上或左的最小代价，再加上当前格子权重。 - 一维滚动时：
dp[j]表示从上方来的最小和dp[j-1]表示从左方来的最小和（因为已更新到当前行）- 所以
dp[j] = min(dp[j], dp[j-1]) + grid[i][j]。
类似题目（网格最短路 DP：来自上/左取 min）
dp[j] = min(dp[j], dp[j-1]) + cost[i][j]
5. 最长回文子串
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
最优解（中心扩展：每个中心向两边扩，O(n^2) 时间 O(1) 空间）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 回文的定义：左右对称。
- 关键推理：最长回文一定有一个“中心”：
- 奇数长度回文中心是一个字符（比如
aba的中心是 b） - 偶数长度回文中心在两个字符之间（比如
abba的中心在 bb 之间）
- 奇数长度回文中心是一个字符（比如
- 所以我们枚举每个可能中心，然后向两边扩展，直到不再相等。
- 为什么是 (O(n^2))：中心有 (O(n)) 个，每次扩展最坏 (O(n))。
- 这题也可以用二维 DP 表
pal[i][j]，同样是 (O(n^2))，中心扩展更省空间、更直观。
类似题目（中心扩展模板）
for center in all:expand(center, center)expand(center, center+1)
1143. 最长公共子序列
给定两个字符串 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仅由小写英文字符组成。
最优解（二维 DP：dp[i][j] 表示前 i/前 j 的 LCS 长度）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 题意：从两个字符串里各挑一些字符（顺序不变、可以不连续），能凑出的最长相同串有多长？这就是「最长公共子序列」。
- 想法：
dp[i][j]表示：只看text1的前 i 个、text2的前 j 个，这段里最长公共子序列的长度。 - 怎么算？看「最后一个字符」：
- 一样：这两个字符可以一起算进公共子序列，长度就是「前面那段的答案 + 1」，即
dp[i][j] = dp[i-1][j-1] + 1。 - 不一样：这两个里至少有一个不能配对。那就看两种选择谁更大：不用 text1 的最后一个（相当于
dp[i-1][j]），或不用 text2 的最后一个（相当于dp[i][j-1]），取较大值：dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
- 一样：这两个字符可以一起算进公共子序列，长度就是「前面那段的答案 + 1」，即
类似题目（字符串二维 DP：末尾相同走对角，不同取上/左 max）
套路一样：看两串「末尾」是否相同，相同就对角 +1，不同就从上/左取最大：
if (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
72. 编辑距离
给你两个单词 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由小写英文字母组成
最优解（二维 DP：插入/删除/替换 三选一）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 编辑距离定义：把 word1 变成 word2 的最少操作数（插入、删除、替换）。
- 状态定义：
dp[i][j]表示把word1前 i 个字符变成word2前 j 个字符的最小操作数。 - 初始条件：
dp[i][0]=i：变成空串只能删 i 次dp[0][j]=j：从空串变成长度 j 只能插 j 次
- 转移推理：
- 如果末尾字符相同，不需要操作：
dp[i][j]=dp[i-1][j-1] - 否则末尾要对齐，有三种方式：
- 删除 word1 末尾：
dp[i-1][j] + 1 - 插入 word2 末尾：
dp[i][j-1] + 1 - 替换 word1 末尾为 word2 末尾：
dp[i-1][j-1] + 1取最小。
- 删除 word1 末尾：
- 如果末尾字符相同，不需要操作：
类似题目（编辑类 DP：三操作取 min）
if same: dp[i][j]=dp[i-1][j-1]else dp[i][j]=1+min(del, ins, rep)