学动态规划，先别急着背转移方程
很多人一学动态规划，就想先把方程背下来。
很多人一学动态规划，就想先把方程背下来。
但动态规划真正的入口，通常不是方程，而是状态定义。
为什么背方程不够
因为同一个题型，只要题目稍微换个壳：
- 状态就可能变
- 边界条件就可能变
- 转移含义也会跟着变
如果你记住的只是一个公式，那它很难迁移到下一题。
动态规划最该先写的那句话
我更建议先写一句中文：
dp[i] 或 dp[i][j] 到底表示什么？
这句话如果写不清楚，后面的很多推导都只是在“猜”。
为什么状态定义是根
因为转移方程本质上是在描述：
- 这个状态怎么从更小的问题得到
如果状态本身含义模糊，你根本无法判断：
- 转移是否完整
- 是否有重复
- 是否漏掉边界
一个更稳的顺序
我自己更习惯按这个顺序想：
- 状态是什么
- 选择是什么
- 转移怎么来
- 初始条件是什么
- 最后答案取哪里
这五步里，第一步没稳，后面通常都会摇晃。
结论
动态规划的真正起点不是记公式，而是把状态含义说清楚。
因为只有状态明确了，转移才会真正有根。