🗓️ Day 21: Climbing Stairs Variants

📘 What You’ll Learn

• How to handle different variants of the Climbing Stairs problem
• Dynamic programming for multiple step options
• Recursion vs DP tradeoffs
• Optimizing space
• Real LeetCode examples with 1, 2, or 3 steps

🧠 Concept

You’re climbing stairs again — but this time, you're allowed to take 1, 2, or 3 steps at a time. 🧗‍♂️

It’s similar to the Fibonacci-style problem but more flexible. You’ll compute the number of ways to reach the top using a bottom-up DP approach:

Let:

• dp[i] = number of ways to reach step i

Then:

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

With base cases:

dp[0] = 1

This problem is great for understanding multi-step dynamic programming.

📊 Visualization

If n = 4, how many ways can you reach the top?

You can break it down like this:

dp[4] = dp[3] + dp[2] + dp[1]

And so on recursively:

dp[0] = 1

Step 1: [1]
Step 2: [1,1], [2]
Step 3: [1,1,1], [1,2], [2,1], [3]
Step 4: [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2], [1,3], [3,1]

Total ways = 7

💻 TypeScript Example

function climbStairs(n: number): number {
  if (n < 0) return 0;
  if (n === 0) return 1;

  const dp = Array(n + 1).fill(0);
  dp[0] = 1;

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

  return dp[n];
}

• ⏱️ Time: O(n)
• 💾 Space: O(n) (can optimize to O(1))

🧪 LeetCode Homework

📘 70. Climbing Stairs

You can take 1 or 2 steps at a time. Return the number of distinct ways to reach the top.

📘 746. Min Cost Climbing Stairs

Each step has a cost. Reach the top with minimal cost.

📘 1137. N-th Tribonacci Number

Similar to Fibonacci, but sum of previous 3 terms.

console.log(climbStairs(3)); // 4
console.log(climbStairs(4)); // 7

📌 Key Takeaways

• Dynamic programming scales easily with step size
• Base cases are crucial for recursion & DP
• You can reduce space using sliding variables
• These patterns appear in tiling, paths, and more!

🔮 Up Next

▶️ Day 22: Frog Jump with Minimum Energy