爬楼梯回顾

把状态和转移写成一个从小往大的循环，就是最干净的 DP 写法——递推式 DP（自底向上），连递归都不用。

int climb(int n){
    vector<int> dp(n+1);
    dp[1]=1; dp[2]=2;               // 边界
    for(int i=3;i<=n;i++)
        dp[i]=dp[i-1]+dp[i-2];      // 由小状态推大状态
    return dp[n];
}

从 dp[1]、dp[2] 出发，一步步把 dp[3]、dp[4]…… 填满，答案就在 dp[n]。

和记忆化的关系

记忆化是"自顶向下"（从 $n$ 往回问），递推是"自底向上"（从小往大填），两者算的是同一张表，复杂度都是 $O(n)$。递推没有递归开销、常数更小，是竞赛里更常用的写法。

顺手的优化

dp[i] 只用到前两个值，可以只留两个变量滚动，空间从 $O(n)$ 降到 $O(1)$。