🧩
多维动归
5 篇文章 · 已读 0 / 5
查看专题概览 / 复习建议
共 5 题
核心套路
- 二维 DP：
dp[i][j]通常对应两个序列 / 一个矩阵的子问题 - 路径数 / 最小代价：从左上 / 右下递推
- 字符串类（编辑距离、最长公共子序列）：对两个串各开一维
题目列表
| 题号 | 题目 | 难度 | 状态 |
|---|---|---|---|
| 62 | 不同路径 | 🟡 Medium | ⬜ |
| 64 | 最小路径和 | 🟡 Medium | ⬜ |
| 5 | 最长回文子串 | 🟡 Medium | ⬜ |
| 1143 | 最长公共子序列 | 🟡 Medium | ⬜ |
| 72 | 编辑距离 | 🟡 Medium | ⬜ |
易错点速查
- 5 最长回文：中心扩展 O(n²) 比 DP 更简洁，Manacher O(n) 进阶题再背
- 1143：
dp[i][j] = dp[i-1][j-1] + 1if 相等 elsemax(dp[i-1][j], dp[i][j-1]) - 72：三种操作对应三个前驱：
dp[i-1][j-1]+替换、dp[i-1][j]+删除、dp[i][j-1]+插入 - 边界：第 0 行 / 第 0 列 = 0 或对应初值