LeetCode 70：爬楼梯，从 dp[i] 含义推出一维 DP

题目要求

输入输出

• 输入：整数 n
• 含义：爬到第 n 阶楼顶
• 每次可以爬 1 或 2 阶
• 输出：返回到达楼顶的不同走法数量
• 约束：1 <= n <= 45

示例

输入：n = 2
输出：2
解释：1+1，2

输入：n = 3
输出：3
解释：1+1+1，1+2，2+1

这篇只用 Python，从 dp[i] 的含义一步一步推出最终代码。

从 n = 3 的最后一步开始

先看最小能暴露转移的例子：

n = 3

到第 3 阶的最后一步只可能来自：

• 第 2 阶，再走 1 阶
• 第 1 阶，再走 2 阶

所以“到第 3 阶的方法数”不是凭空算出来的，而是来自两个更小的位置。

Step 1：先定义更小的问题

直接问“到第 n 阶有几种走法”太大。先定义：

dp[i] = 到达第 i 阶的方法数

注意这里的 i 是楼梯位置，不是数组下标含义上的第几个元素。

先写最小骨架：

def climb_stairs(n: int) -> int:
    dp = [0] * (n + 1)

现在这个版本能做到：

• 给 0..n 每个位置预留一个状态。
• 明确 dp[i] 表示“到达第 i 阶”的方法数。

它还缺：

• 起点和第 1 阶的 base case。
• 后续位置的转移。

Step 2：补上起点和第 1 阶

在上一版基础上，先填 base case。

站在第 0 阶不动，可以理解为“已经在起点”的一种方式：

dp[0] = 1

到第 1 阶只能走 1 阶：

dp[1] = 1

当前代码是：

def climb_stairs(n: int) -> int:
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1

现在这个版本能做到：

• 正确处理 n = 1。
• 让后续转移有合法来源。

它还缺：

• i >= 2 时怎么从前面的位置走过来。

Step 3：第 i 阶只可能来自 i-1 或 i-2

现在看 i >= 2。

如果最后一步走 1 阶，那么上一个位置是 i - 1。 如果最后一步走 2 阶，那么上一个位置是 i - 2。

这两类走法不会重叠，因为最后一步长度不同。

因此转移是 dp[i] = dp[i - 1] + dp[i - 2]。¹

在上一版基础上新增这个转移：

for i in range(2, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

当前代码是第一版完整正确表格解法：

def climb_stairs(n: int) -> int:
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

现在这个版本能做到：

• 正确计算每个楼梯位置的方法数。
• 直接返回 dp[n]。

它还缺：

• 空间还能优化，因为每次只依赖前两个状态。

Step 4：慢速走一遍表

以 n = 5 为例：

这张表要看的重点是：

dp[i] 的含义始终是“到达第 i 阶的方法数”，而不是“第 i 步怎么走”。

Step 5：把 dp 数组压成两个变量

上一版的转移是：

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

它只依赖前两个位置。把它们记为：

• prev2：dp[i - 2]
• prev1：dp[i - 1]

在上一版基础上，用两个变量替换整张表：

prev2 = 1
prev1 = 1

for _ in range(2, n + 1):
    cur = prev1 + prev2
    prev2 = prev1
    prev1 = cur

最终完整代码是：

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1

        prev2 = 1
        prev1 = 1

        for _ in range(2, n + 1):
            cur = prev1 + prev2
            prev2 = prev1
            prev1 = cur

        return prev1


if __name__ == "__main__":
    print(Solution().climbStairs(2))
    print(Solution().climbStairs(3))

现在这个版本能做到：

• 保持和 dp 表版本一样的状态转移。
• 把额外空间从 O(n) 降到 O(1)。

它还缺：

• 如果题目允许一次走更多阶，转移来源就不再只有两个；本题只允许 1 或 2 阶。

正确性

不变量：

• 处理到位置 i 时，prev1 等于 dp[i]，prev2 等于 dp[i - 1]。

为什么转移正确：

• 任何到达第 i 阶的走法，最后一步只能是 1 阶或 2 阶。
• 最后一步是 1 阶的走法数等于 dp[i - 1]。
• 最后一步是 2 阶的走法数等于 dp[i - 2]。
• 两类最后一步不同，不会重复，所以相加。

复杂度

• 时间复杂度：O(n)。
• 额外空间：O(1)。

常见错误

• 把 dp[0] 设成 0，导致 n = 2 算不出两种走法。
• 忘记单独处理 n = 1，空间优化版本可能返回未定义的 cur。
• 把 dp[i] 理解成“第 i 步选择什么”，而不是“到达第 i 阶的方法数”。

小结

• 一维 DP 的第一步是写清 dp[i] 的含义。
• 爬楼梯里，dp[i] 表示到达第 i 阶的方法数。
• 第 i 阶只可能来自 i - 1 或 i - 2。
• 空间优化只是把 dp[i - 2] 和 dp[i - 1] 留成两个变量。

参考与延伸

• LeetCode 70：Climbing Stairs
• LeetCode 746：Min Cost Climbing Stairs
• LeetCode 198：House Robber

Notes

• 题意、示例和约束参考 LeetCode 70 的公开题目摘要。
• 代码语言按本仓库当前 LeetCode 教程默认选择 Python。