LeetCode 70 - Climbing Stairs

This is an Easy dynamic programming problem about counting how many ways there are to climb to the top when each move can be either 1 step or 2 steps. It is a useful example for seeing why plain recursion repeats work and how memoization removes that repetition.

---

Problem link and explanation

• Problem link: 70. Climbing Stairs
• Summary: Given a natural number n, return the number of distinct ways to reach exactly the n-th stair when each move can climb either 1 step or 2 steps.

For n = 2, there are two ways.

1 + 1
2

For n = 3, there are three ways.

1 + 1 + 1
1 + 2
2 + 1

At any current stair, the only choices are moving to the next stair or skipping one stair. That makes recursion a natural first approach: from the current position, split into the 1-step branch and the 2-step branch.

---

Approach

1. Split the cases with recursion

Let the current stair be step. From there, the next states are step + 1 and step + 2. The number of ways from the current position is the sum of the ways from those two next positions.

There are two base cases. If step equals n, the path has reached the target exactly, so it returns 1. If step is greater than n, the path has overshot the target, so it returns 0.

class Solution:
    def climb_rec(self, n: int, step: int, memo: Dict[int, int]):
        if step > n:
            return 0
        if step == n:
            return 1

        first_way = self.climb_rec(n, step + 1, memo)
        second_way = self.climb_rec(n, step + 2, memo)
        return first_way + second_way

This expresses the problem directly, but it repeats work when multiple paths reach the same step.

For example, when n = 4, the plain recursive calls spread out roughly like this.

climb(0)
├── climb(1)
│   ├── climb(2)
│   │   ├── climb(3)
│   │   │   ├── climb(4) ✓
│   │   │   └── climb(5) ✗
│   │   └── climb(4) ✓
│   └── climb(3)
│       ├── climb(4) ✓
│       └── climb(5) ✗
└── climb(2)
    ├── climb(3)
    │   ├── climb(4) ✓
    │   └── climb(5) ✗
    └── climb(4) ✓

The calls to climb(2) and climb(3) happen more than once. The number of ways from a specific step to the top does not depend on how that step was reached, so the same subproblem should not be solved again.

2. Reduce repeated work with memoization

To reduce repeated computation, each step can store the number of ways from that position to the top. If the same step appears again, the recursion can return the saved value instead of going deeper.

class Solution:
    def climb_rec(self, n: int, step: int, memo: Dict[int, int]):
        if step > n:
            return 0
        if step in memo:
            return memo[step]
        if step == n:
            return 1

        first_way = self.climb_rec(n, step + 1, memo)
        second_way = self.climb_rec(n, step + 2, memo)
        memo[step] = first_way + second_way
        return memo[step]

The memo dictionary uses step as the key and the number of ways from that position as the value. Once a stair position is computed, later calls can reuse it.

In the provided code, the first move is split outside the recursive helper.

return self.climb_rec(n, 1, memo) + self.climb_rec(n, 2, memo)

That means the solution starts by considering the first 1-step move and the first 2-step move separately. After that, both branches share the same memo. When n = 1, there is only one way to climb, so the function returns 1 immediately.

---

Complexity analysis

• Time complexity: O(n)

  • With memoization, each stair position is computed once, so the runtime grows linearly with n.

• Space complexity: O(n)

  • The memo dictionary stores results for stair positions, and the recursion call stack can also grow up to n levels.

---

Implementation code

The final implementation uses recursion with memoization. Each state adds the result of moving 1 step and 2 steps, then stores the computed value in memo.

from typing import Dict

class Solution:
    def climb_rec(self, n: int, step: int, memo: Dict[int, int]) -> int:
        if step > n:
            return 0

        if step in memo:
            return memo[step]

        if step == n:
            return 1

        first_way = self.climb_rec(n, step + 1, memo)
        second_way = self.climb_rec(n, step + 2, memo)

        memo[step] = first_way + second_way
        return memo[step]

    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1

        memo: Dict[int, int] = {}
        return self.climb_rec(n, 1, memo) + self.climb_rec(n, 2, memo)

---

Summary and reflection

This problem is easy to model recursively because each state has two choices: climb 1 step or climb 2 steps. The problem with plain recursion is that it recalculates the same stair positions multiple times.

Memoization stores the result for each step, so the same subproblem is only solved once. That reduces the time complexity to O(n). The important point is not to store every full path, but to reuse the fact that the number of ways from a specific stair to the top is always the same.