Climbing Stairs
Distinct ways to climb n stairs with 1- or 2-step moves — Fibonacci.
2 min read
dp fibonacci
Problem#
Take 1 or 2 steps at a time. Return the number of distinct ways to reach step n.
Examples#
n = 2→2n = 3→3
Constraints#
1 <= n <= 45.
Approach#
dp[i] = dp[i-1] + dp[i-2]. Roll to two scalars.
Solution#
class Solution {public: int climbStairs(int n) { int a = 1, b = 1; for (int i = 2; i <= n; ++i) { int c = a + b; a = b; b = c; } return b; }};func climbStairs(n int) int { a, b := 1, 1 for i := 2; i <= n; i++ { a, b = b, a+b } return b}class Solution: def climbStairs(self, n: int) -> int: a, b = 1, 1 for _ in range(2, n + 1): a, b = b, a + b return bvar climbStairs = function(n) { let a = 1, b = 1; for (let i = 2; i <= n; i++) { const c = a + b; a = b; b = c; } return b;};class Solution { public int climbStairs(int n) { int a = 1, b = 1; for (int i = 2; i <= n; i++) { int c = a + b; a = b; b = c; } return b; }}function climbStairs(n: number): number { let a = 1, b = 1; for (let i = 2; i <= n; i++) { const c = a + b; a = b; b = c; } return b;}Editorial#
The recurrence is Fibonacci — dp[n] = dp[n-1] + dp[n-2] because the last step is either a 1-step (so we came from n-1) or a 2-step (from n-2).
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#