Saltar al contenido principal

Climbing Stairs

This question is asked by Google. Given a staircase with N steps and the ability to climb either one or two steps at a time, return the total number of ways to arrive at the top of the staircase.

Example(s)​

Example 1:

Input: N = 2
Output: 2
Explanation:
Ways to reach step 2:
  1. 1 step + 1 step
  2. 2 steps
Total: 2 ways

Example 2:

Input: N = 3
Output: 3
Explanation:
Ways to reach step 3:
  1. 1 step + 1 step + 1 step
  2. 1 step + 2 steps
  3. 2 steps + 1 step
Total: 3 ways

Example 3:

Input: N = 4
Output: 5
Explanation:
Ways to reach step 4:
  1. 1 + 1 + 1 + 1
  2. 1 + 1 + 2
  3. 1 + 2 + 1
  4. 2 + 1 + 1
  5. 2 + 2
Total: 5 ways

Example 4:

Input: N = 1
Output: 1
Explanation:
Only one way: 1 step

Solution​

The solution uses Dynamic Programming (Fibonacci sequence):

  1. Recurrence: To reach step N, you can come from step N-1 (1 step) or step N-2 (2 steps)
  2. Base cases: ways(0) = 1, ways(1) = 1
  3. Pattern: ways(N) = ways(N-1) + ways(N-2) - This is the Fibonacci sequence!

JavaScript Solution - Dynamic Programming

/**
* Count ways to climb N steps (1 or 2 steps at a time)
* @param {number} N - Number of steps
* @return {number} - Total number of ways
*/
function climbStairs(N) {
if (N <= 1) return 1;
if (N === 2) return 2;

// dp[i] = number of ways to reach step i
const dp = new Array(N + 1);
dp[0] = 1; // Base case: 1 way to be at ground (start)
dp[1] = 1; // Base case: 1 way to reach step 1
dp[2] = 2; // Base case: 2 ways to reach step 2

// Fill DP table
for (let i = 3; i <= N; i++) {
  // To reach step i, can come from step i-1 (1 step) or step i-2 (2 steps)
  dp[i] = dp[i - 1] + dp[i - 2];
}

return dp[N];
}

// Test cases
console.log('Example 1:', climbStairs(2)); 
// 2

console.log('Example 2:', climbStairs(3)); 
// 3

console.log('Example 3:', climbStairs(4)); 
// 5

console.log('Example 4:', climbStairs(1)); 
// 1
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (Space-Optimized)​

Here's a space-optimized version using only two variables:

/**
 * Space-optimized: O(1) space instead of O(N)
 */
function climbStairsOptimized(N) {
  if (N <= 1) return 1;
  if (N === 2) return 2;
  
  // Only need last two values
  let prev2 = 1; // ways(N-2)
  let prev1 = 2; // ways(N-1)
  
  for (let i = 3; i <= N; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  
  return prev1;
}

Alternative Solution (Recursive with Memoization)​

Here's a recursive solution with memoization:

/**
 * Recursive solution with memoization
 */
function climbStairsRecursive(N, memo = {}) {
  if (N <= 1) return 1;
  if (N === 2) return 2;
  if (memo[N]) return memo[N];
  
  memo[N] = climbStairsRecursive(N - 1, memo) + 
            climbStairsRecursive(N - 2, memo);
  return memo[N];
}

Complexity​

  • Time Complexity: O(N) - We iterate through steps 1 to N once.
  • Space Complexity:
    • Standard DP: O(N) - For the DP array
    • Optimized: O(1) - Using only two variables

Approach​

The solution uses Dynamic Programming (Fibonacci sequence):

  1. Recurrence relation:

    • To reach step N, you can come from step N-1 (taking 1 step) or step N-2 (taking 2 steps)
    • ways(N) = ways(N-1) + ways(N-2)

  2. Base cases:

    • ways(0) = 1 (1 way to be at ground/start)
    • ways(1) = 1 (1 way to reach step 1: take 1 step)
    • ways(2) = 2 (2 ways: 1+1 or 2)

  3. Pattern:

    • This is the Fibonacci sequence! (1, 1, 2, 3, 5, 8, 13, ...)
    • ways(N) = Fibonacci(N+1)

  4. Fill DP table:

    • Build up from base cases to N

Key Insights​

  • Fibonacci sequence: The pattern matches Fibonacci numbers
  • Optimal substructure: Solution uses solutions to subproblems
  • Two choices: At each step, can take 1 or 2 steps
  • O(N) time: Linear time to compute
  • O(1) space: Can optimize to constant space

Step-by-Step Example​

Let's trace through Example 2: N = 3

Base cases:
  ways(0) = 1
  ways(1) = 1
  ways(2) = 2

Compute ways(3):
  ways(3) = ways(2) + ways(1)
          = 2 + 1
          = 3

DP table:
  dp[0] = 1
  dp[1] = 1
  dp[2] = 2
  dp[3] = 3

Result: 3

Ways to reach step 3:
  1. 1 + 1 + 1
  2. 1 + 2
  3. 2 + 1

Visual Representation​

Example 2: N = 3

Step 0 (start)
  ↓
Step 1 ──→ Step 2 ──→ Step 3
  ↓         ↓
Step 2 ──→ Step 3
  ↓
Step 3

Paths:
  0 → 1 → 2 → 3  (1+1+1)
  0 → 1 → 3      (1+2)
  0 → 2 → 3      (2+1)

Total: 3 ways

Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, ...
ways(N) = Fibonacci(N+1)

Edge Cases​

  • N = 0: Return 1 (already at top)
  • N = 1: Return 1 (one way: take 1 step)
  • N = 2: Return 2 (two ways: 1+1 or 2)
  • Large N: Use iterative DP to avoid stack overflow

Important Notes​

  • Fibonacci sequence: This problem is essentially Fibonacci
  • Two choices: Can take 1 or 2 steps at a time
  • Optimal substructure: ways(N) depends on ways(N-1) and ways(N-2)
  • O(N) time: Must compute all values up to N
  • O(1) space: Can optimize to constant space

Why Dynamic Programming Works​

Optimal Substructure:

  • To reach step N, you must first reach step N-1 or N-2
  • The number of ways to reach N is the sum of ways to reach N-1 and N-2
  • This creates the Fibonacci recurrence

Overlapping Subproblems:

  • Multiple paths may reach the same step
  • DP stores and reuses these values

Mathematical Insight​

This problem is equivalent to finding the (N+1)th Fibonacci number:

Fibonacci sequence: F(0)=0, F(1)=1, F(2)=1, F(3)=2, F(4)=3, ...
Ways to climb:      ways(0)=1, ways(1)=1, ways(2)=2, ways(3)=3, ...

ways(N) = F(N+1) where F is Fibonacci sequence starting from F(0)=0, F(1)=1
  • Fibonacci Number: Direct Fibonacci calculation
  • Min Cost Climbing Stairs: Similar with costs
  • Decode Ways: Similar DP pattern
  • Unique Paths: Similar DP problem

Takeaways​

  • Dynamic Programming solves this efficiently
  • Fibonacci pattern appears in many DP problems
  • O(N) time to compute all values
  • O(1) space with optimization
  • Classic DP problem with many variations