多维 DP
62. 不同路径¶
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
核心思路：
状态定义上，设 dp[j] 表示“当前行第 j 列”的路径数量。 由于到达某个格子只可能来自上方或左方，因此状态转移为：
当前格子的路径数 = 上方格子的路径数 + 左方格子的路径数
在实现中：
dp[j] 在更新前，表示“上一行同一列”（上方）的路径数；
dp[j-1] 已经被更新，表示“当前行左边一列”（左方）的路径数；
所以直接执行 dp[j] += dp[j-1] 即可完成转移。
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# dp[j] 表示“当前行第 j 列”的路径数量
dp = [1] * n
for i in range(1, m):
for j in range(1, n):
# 当前行第 j 列的路径数量 = 上一行第 j 列的路径数量dp[j] + 当前行第 j-1 列的路径数量dp[j-1]
dp[j] += dp[j-1]
return dp[-1]
m, n = 3, 4
print(Solution().uniquePaths(m, n))
10
时间复杂度：O(m×n)需要遍历整个网格一次。
空间复杂度：O(n)
64. 最小路径和¶
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
核心思路：
dp[i][j] 表示 从左上角 (0,0) 走到位置 (i,j) 的最小路径和。
由于每一步只能向右或向下移动， 因此到达 (i,j) 只能来自两个方向：
上方：(i-1, j)
左方：(i, j-1)
状态转移方程：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
边界处理：
第一行只能从左边过来 第一列只能从上边过来
from typing import List
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
dp = [0] * n
dp[0] = grid[0][0]
# 初始化第一行
for j in range(1, n):
dp[j] = dp[j-1] + grid[0][j]
# 逐行更新
for i in range(1, m):
dp[0] += grid[i][0] # 第一列只能从上方来
for j in range(1, n):
dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
return dp[-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(Solution().minPathSum(grid))
7
设：
m 为行数； n 为列数
时间复杂度： O(m × n)
空间复杂度： 一维优化，O(n)
5. 最长回文子串¶
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
核心思路
定义状态：
dp[i][j] 表示 子串 s[i:j]（包含 i 和 j）是否是回文串。
状态转移逻辑：
一个字符串是回文，当且仅当：
1）s[i] == s[j]
2）并且内部子串 s[i+1:j-1] 也是回文
因此有：
dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
但要注意长度为 1 和 2 的特殊情况：
长度为 1：一定是回文
长度为 2：只需判断 s[i] == s[j]
因此完整转移为：
如果 s[i] == s[j]：
若 j - i <= 2（长度 ≤ 3），直接是回文
否则 dp[i][j] = dp[i+1][j-1]
关键遍历顺序：
因为 dp[i][j] 依赖 dp[i+1][j-1]， 必须从“短区间”向“长区间”递推。
通常做法：
i 从后往前遍历 j 从 i 向后遍历
from typing import List
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n <= 1:
return s
# dp[i][j] 表示 s[i:j] 是否为回文
dp = [[False] * n for _ in range(n)]
start = 0 # 最长回文起点
max_len = 1
# 单个字符都是回文
for i in range(n):
dp[i][i] = True
# 从后往前枚举左端点
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
if s[i] == s[j]:
# 长度为 2 或 3 时
if j - i <= 2:
dp[i][j] = True
else:
dp[i][j] = dp[i + 1][j - 1]
# 更新最长长度
if dp[i][j] and j - i + 1 > max_len:
max_len = j - i + 1
start = i
return s[start:start + max_len]
s = "bbabbc"
print(Solution().longestPalindrome(s))
bbabb
设字符串长度为 n。
时间复杂度：
O(n²)
因为 i、j 两层循环。
空间复杂度：
O(n²)
因为使用了二维 dp 数组。
第二种解法：
核心思路
回文串具有“中心对称”性质。任意一个回文子串都可以看作围绕某个中心向两侧扩展得到。中心有两种形式：
单个字符为中心（奇数长度回文），例如 "aba"
两个相邻字符为中心（偶数长度回文），例如 "abba"
因此可以枚举每一个可能的中心位置，从该中心向左右扩展，只要左右字符相等就继续扩展，并在扩展过程中更新当前找到的最长回文子串。
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n < 2:
return s
start = 0 # 最长回文子串的起始位置
max_len = 1 # 当前最长回文长度
# 定义中心扩展函数
def expand(left, right):
# 从中心向两侧扩展
while left >= 0 and right < n and s[left] == s[right]:
left -= 1
right += 1
# 循环结束时 s[left] != s[right] 或越界
# 实际有效区间是 (left+1, right-1)
return left + 1, right - 1
for i in range(n):
# 1. 奇数长度回文（单字符为中心）
l1, r1 = expand(i, i)
if r1 - l1 + 1 > max_len:
start = l1
max_len = r1 - l1 + 1
# 2. 偶数长度回文（双字符为中心）
l2, r2 = expand(i, i + 1)
if r2 - l2 + 1 > max_len:
start = l2
max_len = r2 - l2 + 1
return s[start:start + max_len]
s = "bbabbc"
print(Solution().longestPalindrome(s))
bbabb
时间复杂度：O(n²)
外层枚举 n 个中心
每个中心最坏向两侧扩展 O(n)
总体为 O(n²)
在字符串全部相同（例如 "aaaaaa"）时达到最坏情况。
空间复杂度：O(1)
只使用了常数个变量 没有使用额外的二维 DP 表
1143. 最长公共子序列¶
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
核心思路
这是典型的二维动态规划问题。
设 dp[i][j] 表示 text1 前 i 个字符 与 text2 前 j 个字符 的最长公共子序列长度。
关键在于状态划分：
若 text1[i-1] == text2[j-1]
说明当前字符可以加入公共子序列：
dp[i][j] = dp[i-1][j-1] + 1
否则 当前字符无法同时使用，只能删除其中一个：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
边界条件： dp[0][j] = 0 dp[i][0] = 0
因为任意字符串与空串的 LCS 长度为 0。
最终答案是 dp[m][n]。
LCS 的本质是“前缀最优子结构 + 删除决策”。
每一步不是选或不选当前字符，而是选择“删 text1 当前字符”还是“删 text2 当前字符”。
该问题是动态规划中最经典的二维模型之一，与编辑距离问题结构高度相似。
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
# dp[i][j] 表示 text1[:i] 和 text2[:j] 的 LCS 长度
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 练习出错：注意遍历边界，遍历的是dp和text
for i in range(1, m + 1):
for j in range(1, n + 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[-1][-1]
text1 = "macedf"
text2 = "mdface"
print(Solution().longestCommonSubsequence(text1, text2))
4
时间复杂度：O(mn)
双重循环遍历整个 dp 表。
空间复杂度：O(mn)
使用了 (m+1) × (n+1) 的二维数组。
空间优化（滚动数组）
观察转移方程可知： dp[i][j] 只依赖于：
dp[i-1][j]
dp[i][j-1]
dp[i-1][j-1]
因此可以压缩为一维数组。
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [0] * (n + 1)
for i in range(1, m + 1):
prev = 0 # 相当于 dp[i-1][j-1]
for j in range(1, n + 1):
temp = dp[j] # 保存 dp[i-1][j]
if text1[i - 1] == text2[j - 1]:
dp[j] = prev + 1
else:
dp[j] = max(dp[j], dp[j - 1])
prev = temp
return dp[n]
空间复杂度降为 O(n)。
72. 编辑距离¶
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符 删除一个字符 替换一个字符
核心思路
这是典型的二维动态规划问题。
设
dp[i][j] 表示： 将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作数。
状态转移的关键是分析最后一步操作。
若 word1[i-1] == word2[j-1] 说明最后一个字符相同，不需要额外操作：
dp[i][j] = dp[i-1][j-1]
若不相同，则可以有三种操作：
1）删除 word1[i-1] dp[i][j] = dp[i-1][j] + 1
2）插入 word2[j-1] dp[i][j] = dp[i][j-1] + 1
3）替换 word1[i-1] 为 word2[j-1] dp[i][j] = dp[i-1][j-1] + 1
因此总转移方程为：
dp[i][j] = min( dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost )
其中 cost = 0（字符相同）或 1（字符不同）。
边界条件
dp[0][j] = j 空串转换为长度 j 的字符串，需要 j 次插入。
dp[i][0] = i 长度 i 的字符串转换为空串，需要 i 次删除。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
# dp[i][j] 表示 word1[:i] 转换为 word2[:j] 的最小操作数
# 边界必须处理，否则后续涉及到dp[i-1],dp[j-1]的时候会超过边界，取到最后的状态
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 初始化边界
for i in range(m + 1):
dp[i][0] = i # 删除 i 次
for j in range(n + 1):
dp[0][j] = j # 插入 j 次
# 填表
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(
dp[i - 1][j] + 1, # 删除
dp[i][j - 1] + 1, # 插入
dp[i - 1][j - 1] + 1 # 替换
)
return dp[m][n]
word1 = ""
word2 = "ros"
print(Solution().minDistance(word1, word2))
3
复杂度分析
时间复杂度：O(mn)
需要填满 m × n 的 DP 表。
空间复杂度：O(mn)
使用了二维数组。
空间优化（滚动数组）
因为 dp[i][j] 只依赖：
dp[i-1][j]
dp[i][j-1]
dp[i-1][j-1]
可以压缩为一维数组。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = list(range(n + 1)) # 初始化第一行
for i in range(1, m + 1):
prev = dp[0] # dp[i-1][0]
dp[0] = i # 当前行第一列
for j in range(1, n + 1):
temp = dp[j] # 保存旧的 dp[i-1][j]
if word1[i - 1] == word2[j - 1]:
dp[j] = prev
else:
dp[j] = min(
dp[j] + 1, # 删除
dp[j - 1] + 1, # 插入
prev + 1 # 替换
)
prev = temp
return dp[n]
空间复杂度降为 O(n)。