什么是DP

动态规划（DP）是竞赛里最重要的思想之一。核心只有一句话：把大问题拆成小问题，把每个小问题的答案记下来，用过的不再重算。

它什么时候能用

两个前提缺一不可：

• 最优子结构：大问题的最优解，能由小问题的最优解拼出来。
• 重叠子问题：同一个小问题会被反复用到——正因如此，"记下来"才省时间。

一个例子：爬楼梯

一次能上 1 或 2 阶，问上到第 $n$ 阶有多少种走法？

最后一步，要么从 $n-1$ 阶跨 1 阶上来，要么从 $n-2$ 阶跨 2 阶上来，于是：

$$f(n)=f(n-1)+f(n-2)$$

到第 $n$ 阶的走法数（大问题），由到更低阶的走法数（小问题）拼出——这就是最优子结构；而 $f(n-1)$、$f(n-2)$ 又都会用到 $f(n-2)$、$f(n-3)$……重叠子问题也满足。爬楼梯正是最小的 DP 模型，后面的题都是它的放大版。