You are climbing a staircase with n steps. Each move you can climb either 1 step or 2 steps. Return the number of distinct ways to reach the top.
1 + 1 or 2.1 + 1 + 1, 1 + 2, or 2 + 1.- 1 <= n <= 45
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force recursion tries both moves at every step, which makes about 2^n calls because the same subproblems repeat. State: dp[i] = number of ways to reach step i. Recurrence: the last move was 1 step (from i - 1) or 2 steps (from i - 2), so dp[i] = dp[i - 1] + dp[i - 2]. Base cases: dp[1] = 1, dp[2] = 2. Memoising the recursion makes it O(n); filling a table from the bottom up removes the recursion; and since each value only needs the two before it, two variables are enough. It is Fibonacci in disguise.
Algorithm
- If
n <= 2, returnn. - Keep
a = 1(ways to step 1) andb = 2(ways to step 2). - For steps 3 to
n, computec = a + b, then shifta = b,b = c. - Return
b.
O(n)Space: O(1)dp[i] = sum of dp[i - s] over allowed sizes s. For huge n you can use matrix exponentiation in O(log n).class Solution: def climbStairs(self, n: int) -> int: if n <= 2: return n a, b = 1, 2 # ways to reach step i - 2 and step i - 1 for _ in range(3, n + 1): a, b = b, a + b return b