Fibonacci & Climbing Stairs: The Gateway Dynamic Programming Problems

Climbing Stairs is the single best problem to learn dynamic programming: “You can climb 1 or 2 steps at a time — how many distinct ways to reach step n?” The answer is the Fibonacci sequence in disguise. This page derives the recurrence carefully and then shows the classic space optimization from O(n) memory down to O(1).

Defining the DP

To reach step n, your last move was either a 1-step (from step n-1) or a 2-step (from step n-2). Every way to reach n-1 plus every way to reach n-2 together cover all ways to reach n, with no overlap. That gives us the three DP ingredients:

• State: dp[i] = number of distinct ways to reach step i.
• Transition: dp[i] = dp[i-1] + dp[i-2].
• Base cases: dp[0] = 1 (one way to stand still), dp[1] = 1.

This is exactly the Fibonacci recurrence — only the base cases differ.

Tabulation: O(n) time, O(n) space

Fill the table from the base cases upward.

int climbStairs(int n) {
    if (n < 2) return 1;
    std::vector<int> dp(n + 1);
    dp[0] = 1; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

int climbStairs(int n) {
    if (n < 2) return 1;
    int[] dp = new int[n + 1];
    dp[0] = 1; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

function climbStairs(n) {
  if (n < 2) return 1;
  const dp = new Array(n + 1);
  dp[0] = 1; dp[1] = 1;
  for (let i = 2; i <= n; i++)
    dp[i] = dp[i - 1] + dp[i - 2];
  return dp[n];
}

def climb_stairs(n):
    if n < 2:
        return 1
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Space optimization: O(n) time, O(1) space

Each dp[i] depends only on the previous two entries — so we never need the whole array. Keep two rolling variables and slide them forward. This is the rolling-array trick that appears all over DP.

int climbStairs(int n) {
    int prev = 1, cur = 1;          // dp[0], dp[1]
    for (int i = 2; i <= n; i++) {
        int next = prev + cur;
        prev = cur;
        cur = next;
    }
    return cur;
}

int climbStairs(int n) {
    int prev = 1, cur = 1;          // dp[0], dp[1]
    for (int i = 2; i <= n; i++) {
        int next = prev + cur;
        prev = cur;
        cur = next;
    }
    return cur;
}

function climbStairs(n) {
  let prev = 1, cur = 1;            // dp[0], dp[1]
  for (let i = 2; i <= n; i++) {
    const next = prev + cur;
    prev = cur;
    cur = next;
  }
  return cur;
}

def climb_stairs(n):
    prev, cur = 1, 1                # dp[0], dp[1]
    for _ in range(2, n + 1):
        prev, cur = cur, prev + cur
    return cur

For beginners: Notice the loop runs n - 1 times for n >= 2, and the initial cur = 1 already handles n = 0 and n = 1 correctly. Always test the tiny inputs — off-by-one base cases are the most common DP bug.

A variation: stairs with a cost

Many interview versions add a twist — e.g. “you can climb 1, 2, or 3 steps” (just add dp[i-3]), or “each step has a cost, minimize the total.” The skeleton never changes: redefine the state, adjust the transition to take a min/max or extra term, and fix the base cases.

Going deeper: The pure Fibonacci numbers can even be computed in O(log n) with fast matrix exponentiation, but for counting-paths problems the O(n) DP is what generalizes. Recognizing “the answer at step i is a combination of a few earlier steps” is the mental hook that unlocks dozens of harder problems.

Complexity recap

Once this clicks, move on to a problem with real choices and weights: the 0/1 Knapsack. Compare the two implementation styles in memoization vs tabulation.