Climbing Stairs
A staircase has n steps. You may climb one or two steps at a time. Count distinct sequences that reach the top.
Work through the cases
3 examplesInput notation
An integer n from 1 through 45.Expected result
The number of sequences.Case 1
Input
4
Expected output
5
Case 2
Input
1
Expected output
1
Case 3
Input
2
Expected output
2
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
The first idea is recursion: the last step is 1 or 2, so f(n) = f(n-1) + f(n-2). n ≤ 45, and a naive recursion re-expands the same subproblems, which explodes. The bottleneck is overlap. This is the Fibonacci sequence, so we can compute it bottom-up. f[i] depends only on the previous two terms, so two rolling variables suffice: O(n) time and O(1) extra space.
We define f[i] to represent the number of ways to climb to the i-th step, then f[i] can be transferred from f[i - 1] and f[i - 2], that is:
f[i] = f[i - 1] + f[i - 2]
The initial conditions are f[0] = 1 and f[1] = 1, that is, the number of ways to climb to the 0th step is 1, and the number of ways to climb to the 1st step is also 1.
The answer is f[n].
Since f[i] is only related to f[i - 1] and f[i - 2], we can use two variables a and b to maintain the current number of ways, reducing the space complexity to O(1).
The time complexity is O(n), and the space complexity is O(1).
class Solution {
public int climbStairs(int n) {
int a = 0, b = 1;
for (int i = 0; i < n; ++i) {
int c = a + b;
a = b;
b = c;
}
return b;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.