LeetCode: Climbing Stairs— Optimal Solution Explained

LeetCode: Climbing Stairs — Optimal Solution Explained

Table of Content

• Introduction
• Intuition/Solution
• Step-by-Step Visual Guide
• Implementation Code

Introduction

Climbing stairs is a classic problem in computer science and algorithm interviews that is often used to demonstrate the power of dynamic programming.

We’ll explore the climbing stairs problem, break it down into smaller subproblems, and learn how to conquer it using two dynamic programming techniques: memoization (top-down) and tabulation (bottom-up).

This technique showcases an elegant solution with time complexity of O(n) and space complexity of O(n).

Intuition/Solution

The key intuition behind this problem is to recognize that the number of ways to reach the i-th step is the sum of the number of ways to reach the (i-1)-th step and the (i-2)-th step. This is because you can reach the ith step either from the (i-1)-th step (by taking 1 step) or from the (i-2)-th step (by taking 2 steps). Thus, the total number of ways to reach step ‘i’ is the sum of the ways to reach steps ‘i-1’ and ‘i-2’. This observation gives us the following recurrence relation:

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

                Step 3 (1+2=3)
              /        \
             /          \
        Step 1 (1)     Step 2 (1+1=2)
           /            /    \
          /            /      \
      Step 0 (1)  Step 0 (1) Step 1 (1)
                                \
                                 \
                                Step 0 (1)

For example, in let’s say n=3, so we have 3 stairs to climb. Since we can only take 1 or 2 steps at a time. In order to get to step 3, we must be coming from step 2 (3–1) or step 1 (3–2).

Here’s a step-by-step breakdown of the solution

1. Identify the base cases:

• When n = 1, there is only one way to climb the stairs (1 step).
• When n = 2, there are two ways to climb the stairs (1 step + 1 step, or 2 steps).

2. Set up the dynamic programming solution

• Create an array dp of length n+1 to store the number of distinct ways to reach each step.
• Initialize the base cases: dp[1] = 1 and dp[2] = 2

3. Iterate through the array from step 3 to step n, applying the intuition

• For each step i from 3 to n, calculate the number of distinct ways to reach that step as the sum of the number of ways to reach the (i-1)-th step and the (i-2)-th step.
• dp[i]=dp[i-1] + dp[i-2]

4. Return the value at the last index of the dp array

• The value at the last index of the dp array, dp[n], represents the total number of distinct ways to reach the top of the staircase.

Step-by-Step Visual Guide

Example

For n = 6, let’s visualize the array dp and the steps taken at each iteration of the loop:

Initial state:
dp = [0, 1, 2, _, _, _, _]

Iteration 1 (i = 3):
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp = [0, 1, 2, 3, _, _, _]

Iteration 2 (i = 4):
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
dp = [0, 1, 2, 3, 5, _, _]

Iteration 3 (i = 5):
dp[5] = dp[4] + dp[3] = 5 + 3 = 8
dp = [0, 1, 2, 3, 5, 8, _]

Iteration 4 (i = 6):
dp[6] = dp[5] + dp[4] = 8 + 5 = 13
dp = [0, 1, 2, 3, 5, 8, 13]

Final state:
dp = [0, 1, 2, 3, 5, 8, 13]

After the loop, return the value of dp[6], which represents the number of ways to climb 6 steps. In this case, dp[6] = 13, so the output is 13.

Implementation Code

Python

def climb_stairs(n):
    if n <= 2:
        return n

    dp = [0, 1, 2]

    for i in range(3, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])

    return dp[n]

Javascript

function climbStairs(n) {
  if (n <= 2) return n;

  let dp = [0, 1, 2];

  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
}