LeetCode 70 - Climbing Stairs

The problem describes a staircase with n total steps. You start at the bottom and want to reach the top. At every move, you are allowed to climb either 1 step or 2 steps. The goal is to determine how many distinct sequences of moves can take you from the bottom to the top.

leetcodeeasymathdynamic-programmingmemoization

LeetCode Problem 70

Difficulty: 🟢 Easy
Topics: Math, Dynamic Programming, Memoization

Solution

LeetCode 70 - Climbing Stairs

Problem Understanding

The problem describes a staircase with n total steps. You start at the bottom and want to reach the top. At every move, you are allowed to climb either 1 step or 2 steps.

The goal is to determine how many distinct sequences of moves can take you from the bottom to the top.

For example, if n = 3, the valid ways are:

  • 1 + 1 + 1
  • 1 + 2
  • 2 + 1

Even though the total number of steps is the same, different orders count as different ways.

The input consists of a single integer n, representing the number of stairs. The output is a single integer representing the total number of distinct ways to reach exactly the top step.

The constraint 1 <= n <= 45 is important because it tells us several things:

  • The input size is relatively small.
  • Exponential solutions may technically pass for very small values, but they become inefficient quickly.
  • The answer fits safely within a standard 32-bit integer.
  • Dynamic programming is a natural fit because the problem contains overlapping subproblems.

A key observation is that the number of ways to reach a step depends on previous steps. To reach step n, the final move must have come from either:

  • Step n - 1 using a 1 step move
  • Step n - 2 using a 2 step move

This relationship creates the same recurrence as the Fibonacci sequence.

Some important edge cases include:

  • n = 1, where there is only one possible way.
  • n = 2, where there are exactly two ways.
  • Larger values like n = 45, where inefficient recursive solutions become too slow.
  • Ensuring the implementation does not accidentally double-count paths.

Approaches

Brute Force Recursive Approach

The brute force approach tries every possible path recursively.

At each step, the algorithm branches into two choices:

  • Climb 1 stair
  • Climb 2 stairs

The recursion continues until:

  • The exact top is reached, which counts as one valid path.
  • The step count exceeds n, which is invalid.

This approach is correct because it explores every possible combination of moves. However, it repeatedly recomputes the same subproblems.

For example, while computing the answer for n = 5, the algorithm computes the result for n = 3 multiple times through different recursive paths.

This repeated work causes exponential growth in runtime.

Optimal Dynamic Programming Approach

The key insight is that the number of ways to reach step i depends only on the previous two states.

If:

  • dp[i - 1] represents ways to reach step i - 1
  • dp[i - 2] represents ways to reach step i - 2

Then:

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

This works because every valid path to step i must come from one of those two previous steps.

Instead of recomputing values recursively, we build the answer iteratively from smaller subproblems.

Since only the previous two values are needed at any time, we can optimize the space usage to constant space.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Recursively explores all possible paths, many repeated calculations
Optimal O(n) O(1) Dynamic programming with rolling variables

Algorithm Walkthrough

  1. Handle the smallest base cases first.

If n is 1, there is only one possible way to climb the stairs. If n is 2, there are exactly two ways. 2. Store the number of ways for the first two steps.

We initialize two variables:

  • one_step_before = 1
  • two_steps_before = 2

These represent:

  • Ways to reach step 1
  • Ways to reach step 2
  1. Iterate from step 3 up to step n.

For every new step, compute the number of ways using the recurrence relation:

$current = one_step_before + two_steps_before$

This works because:

  • Every path ending at the previous step can add one more stair.
  • Every path ending two steps earlier can add a two-step jump.
  1. Shift the variables forward.

After computing the current answer:

  • The old two_steps_before becomes the new one_step_before
  • The newly computed value becomes the new two_steps_before

This maintains the rolling window of the last two states. 5. Return the final result.

After the loop finishes, two_steps_before contains the answer for step n.

Why it works

The algorithm works because every valid path to step n must end with either:

  • A single step from n - 1
  • A double step from n - 2

These two groups are disjoint and together cover all possibilities. Therefore, the total number of ways is the sum of the counts for the previous two steps.

The dynamic programming approach guarantees correctness because it builds larger answers from already-correct smaller answers.

Python Solution

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

        one_step_before = 1
        two_steps_before = 2

        for _ in range(3, n + 1):
            current = one_step_before + two_steps_before
            one_step_before = two_steps_before
            two_steps_before = current

        return two_steps_before

The implementation begins by handling the smallest valid inputs directly. When n is 1 or 2, the answer is simply n.

Two variables are then initialized to represent the number of ways to reach the first two steps. Instead of storing an entire DP array, the solution keeps only the last two computed values because earlier values are no longer needed.

The loop starts at step 3 and iteratively computes each new state using the recurrence relation. After computing the current number of ways, the variables are shifted forward so the next iteration has access to the most recent two values.

Finally, the variable representing the latest computed step is returned as the answer.

Go Solution

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }

    oneStepBefore := 1
    twoStepsBefore := 2

    for i := 3; i <= n; i++ {
        current := oneStepBefore + twoStepsBefore
        oneStepBefore = twoStepsBefore
        twoStepsBefore = current
    }

    return twoStepsBefore
}

The Go implementation follows the same logic as the Python version. Since Go uses explicit variable declarations, the rolling DP variables are declared using :=.

No special handling for integer overflow is required because the constraint guarantees the result remains within the range of Go's int type.

Unlike Python, Go does not support tuple assignment in the same flexible way, so the code updates variables sequentially using a temporary current variable.

Worked Examples

Example 1

Input:

n = 2

Since n <= 2, the algorithm immediately returns 2.

The two valid paths are:

  1. 1 + 1
  2. 2

Example 2

Input:

n = 3

Initial state:

Variable Value
one_step_before 1
two_steps_before 2

Loop iteration for step 3:

Step current one_step_before two_steps_before
3 1 + 2 = 3 2 3

The algorithm returns 3.

The valid paths are:

  1. 1 + 1 + 1
  2. 1 + 2
  3. 2 + 1

Additional Example

Input:

n = 5

Initial state:

Variable Value
one_step_before 1
two_steps_before 2

Iteration details:

Step current Updated one_step_before Updated two_steps_before
3 3 2 3
4 5 3 5
5 8 5 8

Final answer:

8

Complexity Analysis

Measure Complexity Explanation
Time O(n) The loop runs once for each step from 3 to n
Space O(1) Only a fixed number of variables are stored

The algorithm processes each stair exactly once, so the runtime grows linearly with n.

The space usage remains constant because the solution stores only the previous two DP states instead of maintaining a full array.

Test Cases

solution = Solution()

assert solution.climbStairs(1) == 1  # Minimum valid input
assert solution.climbStairs(2) == 2  # Small base case
assert solution.climbStairs(3) == 3  # First non-trivial recurrence
assert solution.climbStairs(4) == 5  # Fibonacci progression check
assert solution.climbStairs(5) == 8  # Larger recurrence example
assert solution.climbStairs(6) == 13  # Continued DP growth
assert solution.climbStairs(10) == 89  # Medium-sized input
assert solution.climbStairs(20) == 10946  # Larger DP computation
assert solution.climbStairs(45) == 1836311903  # Maximum constraint
Test Why
n = 1 Verifies smallest valid input
n = 2 Verifies second base case
n = 3 Confirms recurrence begins correctly
n = 4 Checks Fibonacci-style accumulation
n = 5 Validates iterative updates
n = 6 Ensures continued correctness
n = 10 Tests medium-sized input
n = 20 Confirms larger dynamic programming state transitions
n = 45 Verifies maximum constraint handling

Edge Cases

Edge Case 1: Single Stair

When n = 1, there is only one valid move possible. A naive implementation that assumes at least two previous states may fail here due to invalid indexing or incorrect initialization.

The implementation handles this correctly with the early return:

if n <= 2:
    return n

Edge Case 2: Two Stairs

When n = 2, there are exactly two possibilities:

  • 1 + 1
  • 2

Some recursive solutions accidentally overcount or undercount this case if the base conditions are not carefully defined.

The implementation directly returns 2, ensuring correctness.

Edge Case 3: Maximum Constraint

The maximum allowed input is n = 45. A brute force recursive solution would perform excessive repeated computations and become extremely slow.

The dynamic programming solution avoids this issue by computing each state exactly once, allowing the implementation to handle the maximum input efficiently.

Edge Case 4: Avoiding Extra Memory Usage

A common DP approach stores all intermediate results in an array. While correct, that approach uses unnecessary memory.

This implementation recognizes that only the previous two values are needed at any point, so it uses rolling variables instead. This guarantees constant auxiliary space while preserving correctness.