Skip to main content

​
核心认知

动态规划不是一套固定模板，而是一种建模方式。 它真正要解决的问题是：
  • 大问题可以拆成小问题
  • 小问题会重复出现
  • 已经算过的结果不要重复算
所以动态规划的核心不在“背代码”，而在“定义状态”。

​
做动态规划时最先想什么

很多人上来就想转移方程，其实顺序反了。 更稳定的顺序通常是：
  1. dp 数组表示什么
  2. 初始状态是什么
  3. 当前状态由谁转移而来
  4. 遍历顺序应该怎么安排
如果第一步没想清楚，后面通常都会乱。

​
一个最基础的 Python 例子

爬楼梯是最适合入门 DP 的题之一。 
def climb_stairs(n: int) -> int:
    if n <= 2:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]
这个例子里最重要的不是代码，而是状态定义：
  • dp[i] 表示到达第 i 阶台阶的方法数
一旦这句话成立，转移方程几乎就会自己出来。

​
动态规划为什么难

动态规划的难点通常集中在这几件事：
  • 状态定义不清楚
  • 转移漏情况
  • 初始化不对
  • 遍历顺序写反
你会发现，DP 题很多时候不是“完全不会”，而是某一个环节没想透。

​
常见题型

动态规划题通常可以分成这些方向：
  • 线性 DP
  • 背包问题
  • 子序列问题
  • 区间 DP
  • 树形 DP
  • 状态压缩 DP
初学阶段最值得先攻克的是：
  • 线性 DP
  • 01 背包
  • 子序列问题

​
动态规划和递归的关系

很多 DP 问题都可以先写成递归。 然后你会发现一些子问题会重复计算，于是：
  • 加缓存，就是记忆化搜索
  • 改成迭代，就是自底向上的动态规划
所以动态规划和递归不是对立关系，而是经常互相转化。

​
动态规划和贪心的区别

贪心在问：
  • 这一步怎么选最优
动态规划在问：
  • 当前状态如何由之前状态推出来
如果题目无法证明“当前最优选择一定正确”，那就应该更认真考虑 DP。

​
学习建议

建议按这个顺序练：
  • 爬楼梯
  • 打家劫舍
  • 不同路径
  • 01 背包
  • 最长递增子序列
  • 最长公共子序列
当你开始习惯先写出“dp[i] 的定义”，动态规划就会从抽象变得具体。