What is the recurrence relation for Climbing Stairs?

The number of ways to reach step n is f(n) = f(n-1) + f(n-2), reflecting the allowed step sizes of 1 or 2.

Can Climbing Stairs be solved using pure recursion?

Yes, but without memoization, recursion has exponential time complexity and will fail for larger n.

How can I reduce space in the DP solution?

Keep only the last two computed values and update iteratively to reduce space from O(n) to O(1).

What is the time complexity of iterative DP for Climbing Stairs?

Iterative DP runs in O(n) time since each step is calculated exactly once using previous results.

How does the problem exemplify state transition dynamic programming?

Each step depends on previous states, making f(n) a direct sum of f(n-1) and f(n-2), the core state transition pattern.

#70

Easy

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？示例 1：输入： n = 2 输出： 2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶示例 2：输入： n = 3 输出： 3 解释：有三种方法…

数学动态规划记忆化

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

1 <= n <= 45

lightbulb

解题思路

方法一：递推

我们定义 $f[i]$ 表示爬到第 $i$ 阶楼梯的方法数，那么 $f[i]$ 可以由 $f[i - 1]$ 和 $f[i - 2]$ 转移而来，即：

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

初始条件为 $f[0] = 1$ ， $f[1] = 1$ ，即爬到第 0 阶楼梯的方法数为 1，爬到第 1 阶楼梯的方法数也为 1。

答案即为 $f[n]$ 。

由于 $f[i]$ 只与 $f[i - 1]$ 和 $f[i - 2]$ 有关，因此我们可以只用两个变量 $a$ 和 $b$ 来维护当前的方法数，空间复杂度降低为 $O(1)$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return b

speed

复杂度分析

指标	值
时间	complexity is O(n) for iterative or memoized DP, since each step is computed once. Space complexity is O(n) for the DP array or memoization table, reducible to O(1) with two-variable optimization. The recurrence ensures linear growth without recomputation.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Asks for the number of ways to reach step n using allowed steps.
question_mark
Hints at using previous step results, indicating dynamic programming pattern recognition.
question_mark
Tests understanding of optimizing space from DP array to constant variables.

warning

常见陷阱

外企场景

error
Attempting plain recursion without memoization leads to exponential time complexity.
error
Confusing step sequences, double-counting combinations instead of counting distinct paths.
error
Ignoring base cases or incorrectly initializing dp array, causing off-by-one errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Changing allowed steps to 1, 2, or 3 alters the state transition and requires adjusting the DP recurrence.
arrow_right_alt
Finding minimum steps to reach the top instead of counting distinct ways changes the problem to a min-path DP variant.
arrow_right_alt
Adding constraints like broken steps introduces conditional checks in the transition formula.

help

常见问题

外企场景

继续练习

#241 为运算表达式设计优先级 #464 我能赢吗 #509 斐波那契数