参考答案
内容深度:适中 · 无代码示例 · 来源:外部链接 · 已复核 · 28 天前更新
核心
- 把原问题拆成可复用的子问题,定义状态
dp[...] 表示「前 i 个/容量 j/区间 [l,r]」的最优值;用状态转移复用子结果,避免指数级重复计算。
- 适用:最优子结构 + 重叠子问题;不满足无后效性时要扩状态(如股票题加「是否持有」)。
步骤
- 定义状态含义 → 写转移 → 初始化边界 → 确定遍历顺序(保证依赖先算)→ 返回目标;可用记忆化搜索自顶向下,或滚动数组压维。
经典
- 0/1 背包、完全背包、LCS、LIS、编辑距离、区间 DP、树形 DP;复杂度通常「状态数 × 转移代价」。
- 常见坑:状态定义漏维度、边界/空集、遍历顺序错、把贪心当 DP;先写暴力递归再优化。