DP 2. Climbing Stairs | Learn How to Write 1D Recurrence Relations

Welcome to Chapter 2 of the Dynamic Programming series. In this lecture, we tackle the classic Climbing Stairs problem. More importantly, we establish a robust, universal 3-step mental framework for converting any unknown problem into a recursive recurrence relation, which forms the bedrock of all Dynamic Programming solutions.

1. Why Do We Need This? (The Problem Statement)

You are given an integer $n$, which represents the total number of stairs you need to climb. Initially, you stand at the 0th stair (ground level), and your objective is to reach the nth stair.

Rules of Movement

• At any given step, you have the flexibility to climb either 1 single step or 2 steps at a time.
• You must compute the total number of distinct ways to travel from the 0th stair to the nth stair.

Concrete Example ($n = 3$)

Let's analyze all distinct paths to reach stair 3 starting from stair 0:

1. 0 -> 1 -> 2 -> 3: Take 1 step, then 1 step, then 1 step.
2. 0 -> 2 -> 3: Take 2 steps, then 1 step.
3. 0 -> 1 -> 3: Take 1 step, then 2 steps.

Thus, for $n = 3$, there are 3 distinct ways to reach the top.

2. Recognizing Dynamic Programming & Recursion

Before applying Dynamic Programming, you must identify when a problem lends itself to DP. Look for these hallmark indicators:

1. Counting Combinations: The problem asks to "count the total number of ways" to achieve an objective.
2. Optimization Queries: The problem asks to find the minimum or maximum output among multiple valid paths.

Real-Life Analogy: Exploring Every Branch

Mental Hook: Imagine standing at a maze fork where you can take Corridor A or Corridor B. To know how many exit paths exist, you must explore both corridors to their absolute ends and add the valid exits together. This exhaustive search behavior is the defining characteristic of Recursion.

Once recursion explores all possible branches, DP steps in to prevent redundant calculations by caching (memoizing) results.

3. The Universal 3-Step Trick to Write Recurrence Relations

To master 1D Dynamic Programming, master this universal blueprint. Memorize and apply these three steps to any recurrence problem:

4. Applying the 3-Step Framework to Climbing Stairs

Let's apply our blueprint step-by-step to the Climbing Stairs problem.

Step 1: Represent in Terms of an Index

Let our function f(index) represent the total number of distinct ways to reach the index-th stair starting from the 0th stair. Here, index ranges from 0 to n.

Step 2: Perform All Possible Choices at the Index

From any given stair, the problem statement allows two choices:

• Jump 1 step forward (index - 1 if going top-down, or index + 1 if going bottom-up).
• Jump 2 steps forward (index - 2 or index + 2).

Step 3: Sum Up All Choices (Counting Ways)

Since the problem asks for total distinct ways, we sum the results of all valid choices:

5. Writing the Naive Recursive Solution

Translating our recurrence relation into code yields a clean recursive function:

function countDistinctWays(n: number): number {
    // Base Cases
    if (n === 0) return 1; // Exactly 1 way to stay at ground/reach 0
    if (n === 1) return 1; // Exactly 1 way to reach stair 1 (0 -> 1)

    // Choice 1: Take 1 step + Choice 2: Take 2 steps
    return countDistinctWays(n - 1) + countDistinctWays(n - 2);
}

Flow Walkthrough for $n = 3$

6. Edge Cases and Handling Sub-Zero Indices

When writing recursive relations involving subtractions like index - 2, always evaluate boundary conditions.

• If we stand at stair 1 and try to take 2 steps backward (1 - 2 = -1), we fall off the stairs into an invalid state.
• Base Case Safeguard:
  • If n === 0, return 1.
  • If n === 1, return 1.
  • If n < 0, return 0 (representing an invalid path that contributes zero ways).

7. Connection to the Fibonacci Sequence

Notice the structural recurrence of our climbing stairs solution:

• $f(0) = 1$
• $f(1) = 1$
• $f(n) = f(n-1) + f(n-2)$

This is mathematically identical to the Fibonacci Number Sequence (shifted by index offset). Because we established a rigorous recurrence relation using our 3-step method, we successfully transformed an unknown stair-climbing puzzle into a well-known mathematical sequence without guessing.

8. Industry Reality & Large-Scale Constraints ($n = 10^{18}$)

While standard memoization, tabulation, and space-optimized linear loops (O(n) time, O(1) space) work for small inputs, real-world platforms like CodeStudio introduce extreme constraints:

• Constraint: $n$ can be as large as $10^{18}$.
• Failure Mode: A standard O(n) loop or tabulation approach will result in a Time Limit Exceeded (TLE) error because iterating $10^{18}$ times takes centuries of CPU cycles.
• Advanced Solution: For Fibonacci-like recurrences where $n \le 10^{18}$, linear solutions are inadequate. You must employ Matrix Exponentiation or mathematical matrix multiplication tricks to compute the result in logarithmic time $\mathcal{O}(\log n)$.

Summary and Key Takeaways

• Universal 3-Step Framework: Always structure DP problems by (1) defining the state/index, (2) exploring all allowed choices, and (3) applying the aggregation function (sum for counts, min/max for optimization).
• Core Recurrence: Climbing stairs with choices of 1 or 2 steps yields the recurrence relation $f(n) = f(n-1) + f(n-2)$.
• Base Cases Matter: Ground level ($n=0$) and stair one ($n=1$) serve as foundational anchor points returning 1.
• Recursion as Exploration: Recursion acts as an exhaustive search engine; Dynamic Programming elevates it by caching overlapping subproblems.
• Fibonacci Equivalence: The climbing stairs problem maps directly to the Fibonacci sequence through systematic recurrence derivation.
• Constraint Awareness: Watch out for massive constraints ($n = 10^{18}$), where linear O(n) loops fail and advanced techniques like matrix exponentiation are required.