1. Climbing Stairs (LeetCode)
Model answer
The task
Count how many distinct ways there are to reach the top of a staircase with n steps when each move advances either one or two steps.
Key idea
To reach step i, the last move must come from step i - 1 or i - 2. Thus the number of ways to reach i is the sum of the ways to reach those two earlier steps. Only the previous two counts are needed, so there is no need to store a full table.
Approach
- Set the number of ways to reach step
0to1, representing the single empty sequence of moves. - Set the number of ways to reach step
1to1. - For each step from
2throughn, add the counts for the preceding two steps. - Return the count for step
n.
class Solution:
def climbStairs(self, n: int) -> int:
# Ways to reach steps 0 and 1.
two_back = 1
one_back = 1
# Build the count using the two preceding results.
for _ in range(2, n + 1):
current = two_back + one_back
two_back = one_back
one_back = current
return one_back
Complexity:
- Time: O(n), since each step is processed once.
- Space: O(1), since only two prior counts are retained.
Common follow-ups
- What if each move can advance 1, 2, or 3 steps? Sum the counts for the previous three steps.
- What if the result must be returned modulo a number? Apply the modulus after each addition.
- What if some steps are forbidden? Set their ways count to zero and use dynamic programming for the allowed steps.