什么是DP

动态规划（DP）用来解这样一类问题：大问题能拆成同类的小问题，而且这些小问题会被反复用到。它的核心是两样东西——

• 状态：要记住什么。比如"到第 $i$ 级的走法数 $f_i$"。
• 转移：大状态怎么由小状态算出来。比如 $f_i=f_{i-1}+f_{i-2}$。

只要把每个状态的答案算一次、存进数组，用时直接取，就避免了递归里的重复计算，这正是 DP 快的原因。

int f[N];
f[起点] = 初值;                 // 边界
for (int i = ...; ...; i++)
    f[i] = 由更小下标的 f 组合;  // 转移

爬楼梯、斐波那契是最简单的 DP：状态一维、转移只看前两项。

坑：转移要"无后效性"——算 $f_i$ 时用到的 $f_{i-1},f_{i-2}$ 必须已经算好，所以循环顺序得保证小的先算。边界值算错是 DP 最常见的失误，务必单独验一遍。