LeetCode 70: Climbing Stairs

Problem Restatement

We are given an integer n.

There is a staircase with n steps. Each time, we may climb either:

1. 1 step
2. 2 steps

We need to return how many distinct ways there are to reach the top.

The official constraint is 1 <= n <= 45. (leetcode.com)

Input and Output

Function shape:

def climbStairs(n: int) -> int:
    ...

Examples

For:

n = 2

There are two ways:

1 + 1
2

So the answer is:

2

For:

n = 3

There are three ways:

1 + 1 + 1
1 + 2
2 + 1

So the answer is:

3

For:

n = 4

There are five ways:

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2

So the answer is:

5

First Thought: Recursive Search

A direct way is to think from the current step.

From any position, we can climb either 1 step or 2 steps.

So to count ways to reach step n, we can say:

ways(n) = ways(n - 1) + ways(n - 2)

because the last move must have come from either step n - 1 or step n - 2.

A direct recursive version looks like this:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

This is logically correct, but it recomputes the same values many times.

For example, climbStairs(5) calls climbStairs(4) and climbStairs(3). Then climbStairs(4) also calls climbStairs(3). The same subproblem appears repeatedly.

Key Insight

The number of ways to reach step i depends only on the previous two steps.

To reach step i, the final move must be:

1. From step i - 1, by taking 1 step
2. From step i - 2, by taking 2 steps

So:

dp[i] = dp[i - 1] + dp[i - 2]

This is the Fibonacci pattern.

The base cases are:

dp[1] = 1
dp[2] = 2

Algorithm

If n <= 2, return n.

Otherwise:

1. Let prev2 = 1, the ways to reach step 1.
2. Let prev1 = 2, the ways to reach step 2.
3. For each step from 3 to n, compute:

current = prev1 + prev2

4. Move the two previous values forward.
5. Return prev1.

Correctness

For step i, every valid path must end with either a 1-step move from step i - 1 or a 2-step move from step i - 2.

These two groups do not overlap because their last moves are different. Therefore the total number of ways to reach step i is the sum of the ways to reach step i - 1 and step i - 2.

The algorithm starts with the correct values for steps 1 and 2. Then it computes each later step from the previous two correct values. By induction, every computed value is correct. Therefore the returned value is the number of distinct ways to climb n steps.

Complexity

Implementation

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        prev2 = 1
        prev1 = 2

        for _ in range(3, n + 1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current

        return prev1

Code Explanation

Handle the smallest cases first:

if n <= 2:
    return n

There is one way to climb one step, and two ways to climb two steps.

Then initialize:

prev2 = 1
prev1 = 2

Here:

For each next step:

current = prev1 + prev2

Then slide the window forward:

prev2 = prev1
prev1 = current

Finally:

return prev1

DP Array Version

The same idea can be written with a table.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2

        for step in range(3, n + 1):
            dp[step] = dp[step - 1] + dp[step - 2]

        return dp[n]

This version is easier to visualize, but it uses O(n) space.

Testing

def run_tests():
    s = Solution()

    assert s.climbStairs(1) == 1
    assert s.climbStairs(2) == 2
    assert s.climbStairs(3) == 3
    assert s.climbStairs(4) == 5
    assert s.climbStairs(5) == 8
    assert s.climbStairs(10) == 89
    assert s.climbStairs(45) == 1836311903

    print("all tests passed")

run_tests()