SyntaxPilot
Courses/DSA and Coding Problems/Lesson 62
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 62 of 90

DP 1: Fibonacci, memoization vs tabulation, climbing stairs

queued

These are the notes for DSA episode 62, the start of the dynamic programming chapter. Greedy works only when one choice can be proved safe; when it can't, we remember answers instead of recomputing them. We start from a real-life puzzle (climbing temple steps 1 or 2 at a time), find the recurrence by looking at the last move, write the plain recursion (correct, but 45 steps take seconds and 52 steps hit Time Limit Exceeded), count the calls to see the overlapping subproblems (16 lakh calls for 30 steps), and fix it three ways: memoization (top-down), tabulation (bottom-up) and two variables (O(1) space). Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real.

The problem, in real life

A child climbs the steps to a hilltop temple, one step or two steps per move. In how many different ways can she reach the top? (1, 1, 2 differs from 2, 1, 1.)

Indian poets counted the same thing: rhythms built from short syllables (1 beat) and long syllables (2 beats). Hemachandra wrote the rule down around 1150, decades before Fibonacci's book (1202) made the numbers famous in Europe.

Temple steps In code
Step number n the input n
A move of 1 or 2 steps the two choices
Ways to reach step n ways(n) / dp[n]
Chalking the count on a step storing it in memo[n]

Every word, from zero

  • Recursion: a method that calls itself on a smaller input, with a base case that stops it.
  • Recurrence: an equation that defines an answer through smaller answers: ways(n) = ways(n - 1) + ways(n - 2).
  • Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, … each the sum of the two before. Climbing stairs gives 1, 2, 3, 5, 8, … (shifted by one).
  • Exponential time: work that multiplies by a constant (here about 1.618, the golden ratio φ) with every +1 in the input.
  • Subproblem: a smaller version of the same question (ways(3) inside ways(5)).
  • Overlapping subproblems: the same subproblem is needed many times.
  • Dynamic programming (DP): solve each subproblem once and reuse its answer.
  • Memoization (top-down): recursion plus a notebook (memo array) of answers already found.
  • Tabulation (bottom-up): fill a table from the smallest subproblem upward, no recursion.
  • State: what dp[i] means, in words.
  • Base case: the smallest states whose answers we know directly.
  • ArrayIndexOutOfBoundsException: reading or writing an array index that doesn't exist.

Problem statement

LeetCode 70, Climbing Stairs. You climb a staircase of n steps, 1 or 2 steps at a time. In how many distinct ways can you reach the top?

n Answer Ways
1 1 1
2 2 1+1, 2
3 3 1+1+1, 1+2, 2+1
5 8

Constraint: 1 ≤ n ≤ 45.

The recurrence. The last move was 1 step (from step n - 1) or 2 steps (from step n - 2), so ways(n) = ways(n - 1) + ways(n - 2), with ways(1) = 1, ways(2) = 2.

Obvious idea: plain recursion

import java.util.*;

public class Main {
    static long calls = 0;
    static long climbStairs(int n) {
        calls++;
        if (n <= 2) return n;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
    public static void main(String[] args) {
        System.out.println("1 step: " + climbStairs(1));
        System.out.println("2 steps: " + climbStairs(2));
        System.out.println("3 steps: " + climbStairs(3));
        System.out.println("5 steps: " + climbStairs(5));
    }
}
1 step: 1
2 steps: 2
3 steps: 3
5 steps: 8

Correct. Now with a timer and the call counter for 30, 45 and 52 steps:

        for (int n : new int[]{30, 45, 52}) {
            calls = 0;
            long t0 = System.nanoTime();
            long w = climbStairs(n);
            long ms = (System.nanoTime() - t0) / 1000000;
            System.out.println(n + " steps: " + w + " ways, " + calls + " calls, " + ms + " ms");
        }
30 steps: 1346269 ways, 1664079 calls, 3 ms
45 steps: 1836311903 ways, 2269806339 calls, 3437 ms

…and then Time Limit Exceeded on 52 steps (times vary by machine).

Why: the same question again and again

The calls made by ways(5):

                 ways(5)
               /         \
          ways(4)         ways(3)
          /     \         /     \
     ways(3)  ways(2)  ways(2)  ways(1)
      /    \
 ways(2)  ways(1)

ways(3) is solved twice and ways(2) three times. For 30 steps there are only 30 different questions but 16,64,079 calls. Each extra step multiplies the work by about 1.618: exponential.

Fix 1: memoization (top-down)

Write each answer down the first time; read it afterwards. Every count is at least 1, so memo[n] == 0 means "not known yet".

import java.util.*;

public class Main {
    static long calls = 0;
    static long[] memo;
    static long climbStairs(int n) {
        memo = new long[n + 1];
        return ways(n);
    }
    static long ways(int n) {
        calls++;
        if (n <= 2) return n;
        if (memo[n] != 0) return memo[n];
        memo[n] = ways(n - 1) + ways(n - 2);
        return memo[n];
    }
    public static void main(String[] args) {
        for (int n : new int[]{30, 45, 52, 90}) {
            calls = 0;
            long w = climbStairs(n);
            System.out.println(n + " steps: " + w + " ways, " + calls + " calls");
        }
    }
}
30 steps: 1346269 ways, 57 calls
45 steps: 1836311903 ways, 87 calls
52 steps: 53316291173 ways, 101 calls
90 steps: 4660046610375530309 ways, 177 calls

57 calls instead of 16 lakh: each step is worked out once (about 2n calls).

Watching the notebook fill up

The same memo, printing every write and every read, for 6 steps:

import java.util.*;

public class Main {
    static long[] memo;
    static long ways(int n) {
        if (n <= 2) return n;
        if (memo[n] != 0) {
            System.out.println("  read  memo[" + n + "] = " + memo[n]);
            return memo[n];
        }
        memo[n] = ways(n - 1) + ways(n - 2);
        System.out.println("wrote memo[" + n + "] = " + memo[n]);
        return memo[n];
    }
    public static void main(String[] args) {
        memo = new long[7];
        System.out.println("ways(6) = " + ways(6));
    }
}
wrote memo[3] = 3
wrote memo[4] = 5
  read  memo[3] = 3
wrote memo[5] = 8
  read  memo[4] = 5
wrote memo[6] = 13
ways(6) = 13

The recursion dives to the bottom first, writes each answer once, and every repeat is a cheap read.

Fix 2: tabulation (bottom-up)

import java.util.*;

public class Main {
    static long climbStairs(int n) {
        if (n <= 2) return n;
        long[] dp = new long[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
    public static void main(String[] args) {
        System.out.println("1 step: " + climbStairs(1));
        System.out.println("2 steps: " + climbStairs(2));
        System.out.println("3 steps: " + climbStairs(3));
        System.out.println("5 steps: " + climbStairs(5));
        System.out.println("45 steps: " + climbStairs(45));
        System.out.println("90 steps: " + climbStairs(90));
    }
}
1 step: 1
2 steps: 2
3 steps: 3
5 steps: 8
45 steps: 1836311903
90 steps: 4660046610375530309
i 1 2 3 4 5 6
dp[i] 1 2 3 5 8 13

Fix 3: two variables, O(1) space

Each cell uses only the two before it. a and b are the ways to reach the two previous steps (the ground and step 1 both have 1 way).

import java.util.*;

public class Main {
    static long climbStairs(int n) {
        long a = 1, b = 1;
        for (int i = 2; i <= n; i++) {
            long c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
    public static void main(String[] args) {
        System.out.println("1 step: " + climbStairs(1));
        System.out.println("2 steps: " + climbStairs(2));
        System.out.println("3 steps: " + climbStairs(3));
        System.out.println("5 steps: " + climbStairs(5));
        System.out.println("45 steps: " + climbStairs(45));
        System.out.println("90 steps: " + climbStairs(90));
    }
}
1 step: 1
2 steps: 2
3 steps: 3
5 steps: 8
45 steps: 1836311903
90 steps: 4660046610375530309

The same solutions in C++

#include <bits/stdc++.h>
using namespace std;

// Climbing Stairs (LeetCode 70): memoization, tabulation and two variables.
vector<long long> memo;
long long ways(int n) {
    if (n <= 2) return n;
    if (memo[n]) return memo[n];
    return memo[n] = ways(n - 1) + ways(n - 2);
}
long long climbMemo(int n) { memo.assign(n + 1, 0); return ways(n); }

long long climbTable(int n) {
    if (n <= 2) return n;
    vector<long long> dp(n + 1);
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

long long climbTwo(int n) {
    long long a = 1, b = 1;
    for (int i = 2; i <= n; i++) { long long c = a + b; a = b; b = c; }
    return b;
}

int main() {
    for (int n : {1, 2, 3, 5, 45, 90})
        cout << n << ": " << climbMemo(n) << " " << climbTable(n) << " " << climbTwo(n) << "\n";
}
1: 1 1 1
2: 2 2 2
3: 3 3 3
5: 8 8 8
45: 1836311903 1836311903 1836311903
90: 4660046610375530309 4660046610375530309 4660046610375530309

The same solutions in Python

from functools import lru_cache

# Climbing Stairs (LeetCode 70). Python ints never overflow.
@lru_cache(maxsize=None)          # memoization in one line
def ways(n):
    return n if n <= 2 else ways(n - 1) + ways(n - 2)

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

def climb_two(n):
    a = b = 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

for n in (1, 2, 3, 5, 45, 90):
    print(n, ways(n), climb_table(n), climb_two(n))
1 1 1 1
2 2 2 2
3 3 3 3
5 8 8 8
45 1836311903 1836311903 1836311903
90 4660046610375530309 4660046610375530309 4660046610375530309

Top-down or bottom-up? A real StackOverflowError

Memoization still recurses, one stack frame per level. With 1 lakh steps on the default Java stack (answers taken modulo 1,000,000,007, a large prime, so the numbers stay small):

import java.util.*;

public class Main {
    static final int MOD = 1_000_000_007;
    static long[] memo;
    static long ways(int n) {
        if (n <= 2) return n;
        if (memo[n] != 0) return memo[n];
        memo[n] = (ways(n - 1) + ways(n - 2)) % MOD;
        return memo[n];
    }
    static long table(int n) {
        long a = 1, b = 1;
        for (int i = 2; i <= n; i++) {
            long c = (a + b) % MOD;
            a = b;
            b = c;
        }
        return b;
    }
    public static void main(String[] args) {
        int n = 100000;
        System.out.println("table: " + table(n));
        memo = new long[n + 1];
        System.out.println("memo:  " + ways(n));
    }
}
table: 967618232
Exception in thread "main" java.lang.StackOverflowError
    at Main.ways(Main.java:9)
    at Main.ways(Main.java:9)
    ...

The table answers instantly; the memo runs out of stack. For deep inputs, prefer bottom-up (or run the recursion in a big-stack thread, episode 58).

How to spot a DP problem: it asks for the number of ways or a min/max; the answer is built from choices made one at a time; and the plain recursion asks the same smaller question more than once.

Three real bugs

Bug 1: the table in int

45 steps: 1836311903
50 steps: -1109825406

The real count for 50 steps is 20,365,011,074 (over 2,000 crore), past Integer.MAX_VALUE. Counting problems grow fast: use long (or take the answer modulo a number when a problem asks for that).

Bug 2: no small-n check before the table

Without if (n <= 2) return n;:

3 steps: 3
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2
    at Main.climbStairs(Main.java:7)
    at Main.main(Main.java:14)

For n = 1 the table has cells 0 and 1 only, and dp[2] = 2 writes past the end.

Bug 3: a memo one cell too short

memo = new long[n];:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
    at Main.ways(Main.java:13)
    at Main.climbStairs(Main.java:8)
    at Main.main(Main.java:18)

Indexes start at 0, so memo[n] needs n + 1 cells.

The DP recipe

  1. State: say what dp[i] means (ways to reach step i).
  2. Recurrence: usually from the last move (dp[i - 1] + dp[i - 2]).
  3. Base cases: dp[1] = 1, dp[2] = 2.
  4. Order: top-down with a memo, or bottom-up with a table.
  5. Shrink: keep only what the recurrence reads (two variables).

Complexity

Approach Time Space 52 steps
Plain recursion O(φⁿ) ≈ O(1.618ⁿ) O(n) stack Time Limit Exceeded
Memoization O(n) O(n) memo + O(n) stack instant
Tabulation O(n) O(n) table instant
Two variables O(n) O(1) instant

Common mistakes

Mistake What you see (real) Why Fix
Plain recursion Time Limit Exceeded at 52 overlapping subproblems memo or table
int table -1109825406 at 50 overflow long
dp[2] = 2 when n = 1 Index 2 out of bounds for length 2 table too small handle n <= 2 first
new long[n] Index 5 out of bounds for length 5 memo[n] needs n + 1 cells new long[n + 1]
Using 0 as "not computed" when 0 is a real answer recomputation (slow) can't tell "0" from "unknown" fill with -1
Forgetting return memo[n] still exponential the notebook is never read check the memo first

Mini project: rhythms of short and long syllables

List every rhythm of n beats made of short (1 beat, S) and long (2 beats, L) syllables, and check the count against the DP.

import java.util.*;

public class Main {
    // Mini project: every rhythm of n beats from S (1 beat) and L (2 beats); count = climbing-stairs number.
    static List<String> rhythms(int n) {
        if (n == 0) return List.of("");
        List<String> out = new ArrayList<>();
        for (String r : rhythms(n - 1)) out.add("S" + r);
        if (n >= 2) for (String r : rhythms(n - 2)) out.add("L" + r);
        return out;
    }
    public static void main(String[] args) {
        for (int n = 1; n <= 5; n++) {
            List<String> r = rhythms(n);
            System.out.println(n + " beats: " + r.size() + " " + r);
        }
    }
}
1 beats: 1 [S]
2 beats: 2 [SS, L]
3 beats: 3 [SSS, SL, LS]
4 beats: 5 [SSSS, SSL, SLS, LSS, LL]
5 beats: 8 [SSSSS, SSSL, SSLS, SLSS, SLL, LSSS, LSL, LLS]

Practice

1. Min Cost Climbing Stairs (LeetCode 746). cost[i] is paid when you step on stair i; start at stair 0 or 1; reach the top (past the last stair) for the least cost.

Solution

dp[i] = least cost to stand on top of position i: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]), dp[0] = dp[1] = 0.

import java.util.*;

public class Main {
    // Min Cost Climbing Stairs (LeetCode 746): two variables.
    static int minCostClimbingStairs(int[] cost) {
        int a = 0, b = 0;            // dp[i - 2], dp[i - 1]
        for (int i = 2; i <= cost.length; i++) {
            int c = Math.min(b + cost[i - 1], a + cost[i - 2]);
            a = b;
            b = c;
        }
        return b;
    }
    public static void main(String[] args) {
        System.out.println(minCostClimbingStairs(new int[]{10, 15, 20}));
        System.out.println(minCostClimbingStairs(new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1}));
    }
}
15
6

2. N-th Tribonacci Number (LeetCode 1137). T(n) = T(n-1) + T(n-2) + T(n-3), T(0) = 0, T(1) = T(2) = 1.

Solution
# N-th Tribonacci Number (LeetCode 1137): three variables.
def tribonacci(n):
    a, b, c = 0, 1, 1
    if n == 0:
        return 0
    for _ in range(n - 2):
        a, b, c = b, c, a + b + c
    return c if n >= 2 else b

print([tribonacci(n) for n in range(8)], tribonacci(25))
[0, 1, 1, 2, 4, 7, 13, 24] 1389537

3. Steps of 1, 2 or 3. How many ways to climb n steps? Hint: ways(n) = ways(n-1) + ways(n-2) + ways(n-3) with ways(0) = 1.

Quick quiz

With steps of 1, 2 or 3, how many ways to climb 4 steps? A) 7 B) 5 C) 8 D) 6

Answer

A) 7. ways(1) = 1, ways(2) = 2, ways(3) = 4, so ways(4) = 4 + 2 + 1 = 7.

Interview questions

  1. What two properties make a problem a DP problem? Overlapping subproblems, and an answer built from answers to subproblems (optimal substructure, for optimisation problems).
  2. Memoization vs tabulation? Top-down recursion with a cache (solves only needed states, uses the call stack) vs bottom-up loops over all states (no recursion, easy to shrink memory).
  3. Why is plain recursion exponential here? Each call makes two more and the same states repeat; the call count grows like Fibonacci (~1.618ⁿ).
  4. How do you get O(1) space? Keep only the states the recurrence reads: the last two.
  5. How would you handle n up to 10^18? Matrix exponentiation of [[1,1],[1,0]] in O(log n), usually modulo a number.
  6. Climbing stairs and Fibonacci: what's the relation? climb(n) = Fib(n + 1) with Fib(1) = Fib(2) = 1.

Glossary

Term Meaning
Recursion A method calling itself on a smaller input
Base case The input answered directly, which stops recursion
Recurrence An answer defined through smaller answers
Fibonacci numbers Each is the sum of the two before
Exponential time Work multiplies with each +1 in the input
Subproblem A smaller version of the same question
Overlapping subproblems The same subproblem needed many times
Dynamic programming Solve each subproblem once, reuse it
Memoization Top-down: recursion + a notebook
Tabulation Bottom-up: fill a table from the base cases
State What dp[i] means
ArrayIndexOutOfBoundsException Accessing an index outside the array

Summary

  • Look at the last move to get the recurrence: ways(n) = ways(n-1) + ways(n-2).
  • Plain recursion repeats subproblems: 16 lakh calls for 30 steps, Time Limit Exceeded at 52.
  • Memoization (top-down), tabulation (bottom-up) and two variables are all O(n) time; the last is O(1) space.
  • Watch for: int overflow, base cases before the table, and arrays of size n + 1.
  • Next episode: house robber: DP with a real choice, take it or skip it.