Climbing Stairs

01 · Question

You are climbing a staircase. It takes n steps to reach the top. Each time you can climb either 1 or 2 steps. Return how many distinct ways you can climb to the top.

Assume n >= 1.

02 · Analysis

For positive n, the final move is one step from n-1 or two from n-2, so ways[n]=ways[n-1]+ways[n-2]. Initialize ways[1]=1 and ways[2]=2. Only two preceding values are needed: O(n) time and O(1) auxiliary space. The displayed contract requires n>=1; a formulation allowing n=0 must define the empty climb separately.

03 · Solution

Reference solution

1def climbStairs(n: int) -> int:
2    if n <= 2:
3        return n
4    a, b = 1, 2
5    for _ in range(3, n + 1):
6        a, b = b, a + b
7    return b

House Robber