Dynamic Programming (1D)

Prev Next

Back in the recursion lesson, naive recursive Fibonacci was the running example of a function that re-solves the same subproblem exponentially many times. Dynamic programming (DP) is exactly the fix for that: recursion plus a systematic way of remembering answers to subproblems you've already solved, so each distinct subproblem is computed once instead of over and over. This lesson covers the two ways to implement that idea — top-down and bottom-up — using Fibonacci as a warm-up and then the "climbing stairs" problem to show the pattern generalizes.

Why Naive Recursion Is Slow: A Quick Recap

fib(5) calls fib(4) and fib(3). But fib(4) itself calls fib(3) again — the exact same subproblem, recomputed from scratch. This branching repeats at every level, giving naive recursive Fibonacci O(2ⁿ) time. DP's insight: there are only n+1 distinct subproblems (fib(0) through fib(n)) — if we remember each one's answer the first time we compute it, every later call becomes an O(1) lookup instead of a re-computation.

Approach 1: Top-Down (Recursion + Memoization)

Keep the same recursive structure, but check a memo (array or HashMap) before recursing, and store the result after computing it. This is the smallest possible change from "naive recursion that works but is slow" to "recursion that's fast" — which is exactly why it's often the easiest way to *discover* a DP solution: write the brute-force recursion first, then add memoization.

public int fibTopDown(int n) {
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1); // -1 means "not computed yet"
    return fibHelper(n, memo);
}

private int fibHelper(int n, int[] memo) {
    if (n <= 1) return n; // base case: fib(0)=0, fib(1)=1
    if (memo[n] != -1) return memo[n]; // already solved this subproblem

    memo[n] = fibHelper(n - 1, memo) + fibHelper(n - 2, memo);
    return memo[n];
}

Time complexity: O(n) — each of the n+1 distinct subproblems (fib(0)..fib(n)) is computed exactly once; every repeat call is an O(1) memo hit. Space complexity: O(n) — the memo array of size n+1, plus O(n) call-stack depth for the recursion itself.

Approach 2: Bottom-Up (Iterative Table Filling)

Instead of recursing downward from n and hoping the base case is reached, start at the base case and iterate upward, filling a dp[] array in order so that by the time you need dp[i], both dp[i-1] and dp[i-2] are already filled in. No recursion, no call stack.

public int fibBottomUp(int n) {
    if (n <= 1) return n;

    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // recurrence: fib(i) = fib(i-1) + fib(i-2)
    }
    return dp[n];
}

Time complexity: O(n) — a single loop from 2 to n, one O(1) addition per iteration. Space complexity: O(n) for the dp array — though it can be reduced to O(1) here by keeping only the last two values instead of the whole array, since fib(i) only ever depends on its two immediate predecessors.

Top-down vs. bottom-up, in practice: top-down is usually easier to derive (start from the brute-force recursion, add a memo) and naturally skips subproblems you never actually need. Bottom-up avoids recursion overhead and stack-depth limits entirely, and makes space optimization (dropping the full array for a few rolling variables) more obvious. Interviewers are usually happy with either; knowing both means you're never stuck if one doesn't click for a given problem.

Generalizing: Climbing Stairs

Problem: You're climbing a staircase with n steps. Each move you can climb either 1 or 2 steps. How many distinct ways are there to reach the top?

Finding the recurrence: think about the last move to reach step n. It was either a 1-step move from step n−1, or a 2-step move from step n−2. Every distinct way to reach step n falls into exactly one of those two cases, and they don't overlap, so the total count is the sum:

ways(n) = ways(n − 1) + ways(n − 2), with ways(0) = 1, ways(1) = 1

This is the exact same recurrence shape as Fibonacci — which is the real point of this example: once you can spot "the answer for n is built from the answers for n−1 and n−2 (or some other small set of smaller subproblems)," you can reuse the identical top-down/bottom-up machinery for a problem that on the surface looks nothing like Fibonacci.

Top-Down

public int climbStairsTopDown(int n) {
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    return climbHelper(n, memo);
}

private int climbHelper(int n, int[] memo) {
    if (n <= 1) return 1; // 1 way to stand still or take one final 1-step
    if (memo[n] != -1) return memo[n];

    memo[n] = climbHelper(n - 1, memo) + climbHelper(n - 2, memo);
    return memo[n];
}

Time complexity: O(n) — n+1 distinct subproblems, each solved once. Space complexity: O(n) for the memo array plus O(n) recursion stack depth.

Bottom-Up

public int climbStairsBottomUp(int n) {
    if (n <= 1) 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];
}

Time complexity: O(n) — one pass filling n−1 table entries with an O(1) addition each. Space complexity: O(n) for the dp array, reducible to O(1) by tracking only the previous two values.

Next: Fibonacci and climbing stairs both have state that depends on a single changing variable (the index i). Many classic DP problems — like comparing two strings or filling a knapsack — have state that depends on two changing variables, which needs a 2D table instead. That's Dynamic Programming (2D).

Prev Next