LeetCode 70: Climbing Stairs Solution in Python Explained

Problem Statement

LeetCode 70, Climbing Stairs, is an easy-level problem where you’re given an integer n representing the number of stairs in a staircase. You can climb either 1 or 2 steps at a time. Your task is to return the number of distinct ways to reach the top (step (n)) as an integer.

Constraints

  • 1 <= n <= 45: Number of stairs is between 1 and 45.

Example

Input: n = 2
Output: 2
Explanation: Ways to climb 2 stairs:
1. 1 step + 1 step
2. 2 steps

Input: n = 3
Output: 3
Explanation: Ways to climb 3 stairs:
1. 1 + 1 + 1
2. 1 + 2
3. 2 + 1

Input: n = 1
Output: 1
Explanation: Only 1 way: 1 step.

Understanding the Problem

How do you solve LeetCode 70: Climbing Stairs in Python? For n = 3, count the distinct ways to reach step 3 using 1 or 2 steps—here, there are 3 ways: [1,1,1], [1,2], [2,1]. This is a combinatorial problem where each step depends on previous choices. We’ll explore two approaches: a Dynamic Programming Solution (optimal and primary) and an Alternative with Fibonacci Formula (elegant and efficient). The DP method runs in O(n) time with O(n) space, while the formula uses O(1) space.

Solution 1: Dynamic Programming Approach (Primary)

Explanation

Use dynamic programming where dp[i] represents the number of ways to reach step (i). Since you can climb 1 or 2 steps, dp[i] = dp[i-1] + dp[i-2] (ways from one step below plus two steps below). Initialize base cases: dp[0] = 1 (one way to stay at 0), dp[1] = 1 (one way to reach 1).

Here’s a flow for (n = 3):

dp[0] = 1 (base)
dp[1] = 1 (base)
dp[2] = dp[1] + dp[0] = 1 + 1 = 2
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
Result: 3
  1. Initialize DP Array.
  • Size \(n+1\), set base cases.
  1. Fill Array.
  • Each step sums ways from 1 and 2 steps back.
  1. Return Result.
  • Value at dp[n].

Step-by-Step Example

Example 1: n = 3

We need 3.

  • Goal: Count ways to climb 3 stairs.
  • Result for Reference: 3.
  • Start: n = 3, dp = [0,0,0,0].
  • Step 1: Initialize base cases.
    • dp[0] = 1, dp[1] = 1.
    • dp = [1,1,0,0].
  • Step 2: Fill array.
    • dp[2] = dp[1] + dp[0] = 1 + 1 = 2.
    • dp[3] = dp[2] + dp[1] = 2 + 1 = 3.
    • dp = [1,1,2,3].
  • Finish: Return dp[3] = 3.

Example 2: n = 2

We need 2.

  • Start: dp = [1,1,0].
  • Step 1: dp[2] = dp[1] + dp[0] = 1 + 1 = 2.
  • Finish: Return dp[2] = 2.

How the Code Works (Dynamic Programming)

Here’s the Python code with line-by-line explanation:

def climbStairs(n: int) -> int:
    # Line 1: Handle base case
    if n <= 2:
        return n

    # Line 2: Initialize DP array
    dp = [0] * (n + 1)
    dp[0] = 1  # Ways to reach step 0
    dp[1] = 1  # Ways to reach step 1

    # Line 3: Fill DP array
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]

    # Line 4: Return number of ways
    return dp[n]

Alternative: Fibonacci Formula Approach

Explanation

Recognize that the problem follows the Fibonacci sequence: the number of ways to reach step (n) is the (n)-th Fibonacci number (with 1-based indexing adjusted). Each step is the sum of the previous two, matching dp[i] = dp[i-1] + dp[i-2]. Use an iterative approach with two variables to compute this in O(n) time and O(1) space.

For (n = 3):

F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3 (adjust for 0-based)
Result: 3
  1. Initialize Fibonacci Variables.
  • prev = 1, curr = 1.
  1. Iterate to (n).
  • Update prev and curr for each step.
  1. Return Result.
  • Final curr value.

Step-by-Step Example (Alternative)

For (n = 3):

  • Start: prev = 1, curr = 1.
  • Step 1: i = 2.
    • next = curr + prev = 1 + 1 = 2, prev = 1, curr = 2.
  • Step 2: i = 3.
    • next = 2 + 1 = 3, prev = 2, curr = 3.
  • Finish: Return curr = 3.

For (n = 2):

  • Start: prev = 1, curr = 1.
  • Step 1: i = 2.
    • next = 1 + 1 = 2, curr = 2.
  • Finish: Return 2.

How the Code Works (Fibonacci Formula)

def climbStairsFib(n: int) -> int:
    # Line 1: Handle base case
    if n <= 2:
        return n

    # Line 2: Initialize Fibonacci variables
    prev, curr = 1, 1

    # Line 3: Iterate to compute nth Fibonacci
    for i in range(2, n):
        prev, curr = curr, curr + prev

    # Line 4: Return number of ways
    return curr

Complexity

  • Dynamic Programming:
    • Time: O(n) – Fill array of size \(n+1\).
    • Space: O(n) – Store DP array.
  • Fibonacci Formula:
    • Time: O(n) – Iterate \(n-2\) times.
    • Space: O(1) – Only two variables.

Efficiency Notes

Fibonacci Formula is O(n) time and O(1) space, more efficient than DP’s O(n) space, making it an excellent choice for LeetCode 70. Both are O(n) time, fitting the constraint of (n \leq 45).

Key Insights

Tips to master LeetCode 70:

  • Fibonacci Link: Recognize the recurrence pattern.
  • DP Basics: Build from base cases up.
  • Space Saving: Use two variables instead of array.

Additional Example

For (n = 4):

  • Goal: 5.
  • DP: [1,1,2,3,5], return 5.
  • Fib: 1,1,2,3,5, return 5.
  • Result: 5.

Edge Cases

  • \(n = 1\): Return 1.
  • \(n = 2\): Return 2.
  • \(n = 45\): Large value, fits 32-bit int (1836311903).

Final Thoughts

The Dynamic Programming solution is a classic pick for LeetCode 70 in Python—intuitive and reliable, with the Fibonacci Formula offering a sleek, space-efficient twist. For a related challenge, try LeetCode 69: Sqrt(x) to switch to math! Ready to climb? Solve LeetCode 70 on LeetCode now and test it with (n=3) or (n=4) to master stair climbing. Dive in and step up!