📐 多维动态规划
状态由两个或多个变量决定（如两个序列的下标、矩阵坐标），通常需要二维 DP 表。
5 题 · 中等 ×5
| # | 题目 | 难度 |
|---|---|---|
| 62 | 不同路径 | 中等 |
| 64 | 最小路径和 | 中等 |
| 5 | 最长回文子串 | 中等 |
| 1143 | 最长公共子序列 | 中等 |
| 72 | 编辑距离 | 中等 |
核心思路
- 不同路径：
dp[i][j] = dp[i-1][j] + dp[i][j-1]，可压缩为一维数组。 - 最小路径和：同上加权，
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。 - 最长回文子串：
dp[i][j]表示s[i..j]是否为回文；dp[i][j] = (s[i]==s[j]) && dp[i+1][j-1]；也可用中心扩展法 O(n²) 时间 O(1) 空间。 - 最长公共子序列：
dp[i][j]=s1[0..i-1]与s2[0..j-1]的 LCS 长度；字符相同则+1，否则取两者删一个的最大值。 - 编辑距离：
dp[i][j]= 将word1[0..i-1]转换为word2[0..j-1]的最少操作数；字符相同则继承，否则取插入/删除/替换三者最小值加 1。