多维动归

共 5 题

核心套路

• 二维 DP：dp[i][j] 通常对应两个序列 / 一个矩阵的子问题
• 路径数 / 最小代价：从左上 / 右下递推
• 字符串类（编辑距离、最长公共子序列）：对两个串各开一维

题目列表

易错点速查

• 5 最长回文：中心扩展 O(n²) 比 DP 更简洁，Manacher O(n) 进阶题再背
• 1143：dp[i][j] = dp[i-1][j-1] + 1 if 相等 else max(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 或对应初值