📘 DP入门总结

✍️ 作者：桑榆
🕓 更新时间：2026-04-02
🧠 关键词：dp、动态规划

DP入门总结

前面刷过几道题，可以分成以下几类

1.线性递推型

特点是：dp[i]通常只依赖前面一两个状态。

典型题：

• 斐波那契数
• 爬楼梯
• 使用最小花费爬楼梯

常见形式：

dp[i] = dp[i - 1] + dp[i - 2]
dp[i] = Math.min(dp[i - 1], dp[i - 2]) + ...

关注点：

• dp[i]表示什么
• 当前状态从前几个状态转移过来
• 初始值是什么

2.选择型 DP

特点是： 当前位置通常有"选"或者"不选"两种决策。

典型题：

• 打家劫舍
• 打家劫舍Ⅱ

核心思路：

dp[i] = Math.max(不选当前, 选当前)

比如打家劫舍：

dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])

3.二维路径型DP

特点是：状态在一个网格里，通常从"上面"或"左边"转移过来。

典型题：

• 不同路径
• 不同路径Ⅱ

常见形式：

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

如果有障碍物，就多一层判断：

if (障碍物) dp[i][j] = 0

关注点：

• dp[i][j]表示到哪个格子的结果
• 当前位置能从哪几个方向过来
• 第一行、第一列怎么初始化

4.枚举分割点型DP

特点是：要求dp[i]时，不是只看前一两个状态，而是要枚举所有切分方式。

典型题：

• 整数拆分
• 不同的二叉搜索树

常见写法：

for (let i = ...; i <= n; i++) {
  for (let j = 1; j < i; j++) {
    // 枚举分割点
  }
}

这类题的关键是： 我把当前问题拆成左右两部分，怎么利用子问题结果？

区别在于：

• 整数拆分：取最大值
• 不同 BST：统计总方案数

5.求最值vs求方案数

这是一个非常重要的横向分类。

求最值的题：

• 使用最小花费爬楼梯
• 打家劫舍
• 整数拆分

特征：

Math.max(...)
Math.min(...)

求方案数的题：

• 爬楼梯
• 不同路径
• 不同的二叉搜索树

特征：

dp[...] += ...
dp[...] = ... + ...