爬楼梯问题如何用动态规划求解？（LeetCode 70）

简化版

爬 n 阶楼梯，每次能上 1 阶或 2 阶，问有多少种不同走法。设 dp[i] 为爬到第 i 阶的走法数，最后一步要么从 i-1 阶跨 1 阶、要么从 i-2 阶跨 2 阶，所以 dp[i] = dp[i-1] + dp[i-2]——正是斐波那契数列。初始 dp[1]=1、dp[2]=2。因为只依赖前两项，可以只用两个变量滚动，做到 O(n) 时间、O(1) 空间。

详细版

int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;                // a = dp[i-2], b = dp[i-1]，从 dp[1]、dp[2] 起
    for (int i = 3; i <= n; i++) {
        int c = a + b;               // dp[i] = dp[i-1] + dp[i-2]
        a = b;
        b = c;
    }
    return b;                        // b = dp[n]
}

状态：dp[i] = 爬到第 i 阶的不同方法数。
转移方程：dp[i] = dp[i-1] + dp[i-2]（到第 i 阶，最后一步只能从 i-1 或 i-2 上来）。
初始化：dp[1] = 1（只有「1」）、dp[2] = 2（「1+1」或「2」）。
状态压缩：只依赖前两项，用两个变量滚动，空间 O(1)。

完整版教学

一、问题与状态定义

爬楼梯：一共 n 阶，每次可以爬 1 阶或 2 阶，问爬到顶（第 n 阶）总共有多少种走法。这是入门级线性 DP，非常适合理解「状态定义 + 转移方程」的套路。

第一步永远是定义状态：令 dp[i] = 「爬到第 i 阶楼梯的不同方法数」。目标就是求 dp[n]。

二、转移方程：dp[i] = dp[i-1] + dp[i-2]

推转移方程的通用技巧是盯住「最后一步」：要到达第 i 阶，最后一步只有两种可能——

从第 i-1 阶爬 1 阶上来；
从第 i-2 阶爬 2 阶上来。

这两种走法互不重叠、且覆盖了所有可能。所以到达第 i 阶的方法数，就是「到达 i-1 阶的方法数」加上「到达 i-2 阶的方法数」：

dp[i] = dp[i-1] + dp[i-2]

这恰好是斐波那契数列的递推式——爬楼梯本质就是斐波那契。

三、初始条件与边界

转移方程从 i=3 才开始用（需要 i-1、i-2 都存在），所以要手工定好前两项：

dp[1] = 1：到第 1 阶只有一种走法（爬 1 阶）。
dp[2] = 2：到第 2 阶有两种（1+1 或一次 2）。

易错点：初始化别只凭直觉。有的写法从 dp[0]=1（地面算一种「什么都不爬」）起步，dp[1]=1，同样能推出 dp[2]=2。只要和状态定义自洽即可，但 dp[1]、dp[2] 的值必须对，否则整条链全错。

四、状态压缩：O(n) 时间 O(1) 空间

dp[i] 只用到紧邻的前两项 dp[i-1]、dp[i-2]，前面更早的值再也用不上。所以完全没必要开一个长度 n 的数组，用两个变量滚动就够：

a 存 dp[i-2]、b 存 dp[i-1]；
每轮算出 c = a + b（即 dp[i]），然后把 a 前移为 b、b 前移为 c。

时间还是 O(n)，空间从 O(n) 降到 O(1)。这是「当前状态只依赖前几个状态」时最常见的空间优化，打家劫舍、斐波那契都用它。

五、本质是斐波那契；常见扩展

每次能爬 1 到 m 阶：转移方程扩展成 dp[i] = dp[i-1] + dp[i-2] + … + dp[i-m]（枚举最后一步爬了几阶），也叫「跳台阶 / 完全背包求排列数」的雏形。
每阶有花费，求最小体力（LeetCode 746）：状态改成「到第 i 阶的最小花费」，转移变 dp[i] = min(dp[i-1], dp[i-2]) + cost[i]。
不同路径、斐波那契、泰波那契：都是同一类「当前项由前几项相加/取最优」的线性 DP，掌握爬楼梯就掌握了这一族。

六、状态语义、转移来源与遍历顺序

本题状态的完整含义是：dp[i] 表示恰好到达第 i 阶的方法数，最后一步只能从 i-1 跨 1 阶或从 i-2 跨 2 阶。

转移过程是：dp[i]=dp[i-1]+dp[i-2]，常用 dp[0]=1, dp[1]=1 统一递推。写代码前应逐个解释转移候选对应题目中的哪种最后选择，并确认这些候选互斥且覆盖全部可能。

定义状态：它概括哪段输入、处于什么决策阶段
列出选择：当前答案的最后一步有哪些来源
写出转移：由已计算的前驱组合当前答案
确定顺序：使用前驱之前不能覆盖它

数字推演：n=5 时序列为 1,1,2,3,5,8，所以到第 5 阶有 8 种，而不是 5 种。

记忆钩子：DP 最容易错的不是 max/min，而是状态少记了信息或一维压缩后读到了本轮新值。

七、初始化、空间压缩与适用边界

实现边界是：题目对 n=0 的返回约定可能不同；结果增长近似 φ^n，int 很快溢出；允许 1..k 步时要累加前 k 个状态。

核对项	本题答案
复杂度	O(n) 时间，滚动变量 O(1) 空间；矩阵快速幂可 O(log n)
基本状态	必须能直接解释为规模 0 或最小输入的真实含义
遍历顺序	由转移依赖决定，不能为了习惯随意正序/倒序
空间压缩	仅在被覆盖状态之后不再需要时安全
结果位置	可能是最后状态、全局最大值或多个终态的聚合

测试应覆盖空/最小输入、不可达状态、全零或负值、答案刚好发生在边界，以及会区分正序与倒序的样例。若需要恢复方案，不能只保留压缩后的数值，还要记录前驱或保留完整状态表。

八、常见误区与追问

误区：dp[0] 必须等于 0。 把“原地不走”视为一种空方案时应为 1，递推才能统一。
误区：状态压缩后可以先覆盖两个旧值。 必须先算 next，再同步平移 prev2、prev1。
误区：答案始终适合 int。 斐波那契增长很快，需要按约束选 long、BigInteger 或取模。
追问：为什么是两个前驱之和？ 所有方案按最后一步长度 1 或 2 分组，互斥且完备。
追问：允许跨 1、3、5 阶怎么办？ 转移改为所有合法步长前驱之和。
追问：求最少步数还是同一转移吗？ 目标从计数变最优，应改为 min 前驱 +1。

九、加强记忆

爬楼梯：dp[i] = 爬到第 i 阶的方法数，盯最后一步（从 i-1 跨 1 阶或从 i-2 跨 2 阶）得转移方程 dp[i]=dp[i-1]+dp[i-2]，就是斐波那契。初始 dp[1]=1、dp[2]=2。只依赖前两项 → 两变量滚动，O(n) 时间 O(1) 空间。扩展：每次爬 1~m 阶就把前 m 项相加；带花费则 dp[i]=min(dp[i-1],dp[i-2])+cost[i]。

简化版

详细版