Dynamic Programming: Turning Exponential Recursion Into Linear Time by Remembering

Quick: what’s the eighth number in the sequence where each one is the sum of the two before it — 1, 1, 2, 3, 5, 8, …? You added 5 and 8 and said 13 without blinking, because you already knew 5 and 8; you didn’t rebuild them. Now picture a version of you cursed to forget every number the instant after you use it. To get the eighth you’d rebuild the seventh from scratch, and to rebuild the seventh you’d rebuild the sixth, and the fifth would get reconstructed over and over down a branching avalanche of repeated work — thousands of additions for a sequence you can actually extend in your sleep.

That gap between the cursed you and the real you is the whole idea behind dynamic programming. It’s just recursion that got tired of solving the same little problem twice. By the end of this article you and I will have taken a function that makes billions of redundant calls and, by adding a single line that remembers, turned it into one that runs in a blink — then done the same trick on a genuinely two-dimensional problem, the kind interviewers actually hand you.

Let’s start nowhere near a computer

Forget code. Picture one of those printed maze puzzles, pen in hand, and the question isn’t just "find a way out" — it’s "how many different ways lead from the entrance to the exit?" The maze isn’t one long tunnel; it’s a web of corridors that keep meeting at the same junctions. And here’s the thing worth staring at: many different routes funnel through the same junction on their way out.

So the first time you work out the answer to "from this junction, how many ways reach the exit?", you do the honest work — you explore every corridor beyond it and count. But you chalk the number right there on the junction. Later, when a completely different route wanders back into that same junction, you don’t re-explore a single corridor. You read the chalk and move on.

That tiny discipline has two halves, and they are the two halves of every dynamic-programming problem:

• Optimal substructure. The answer for a junction is built out of the answers for the junctions it leads to — the big question is made of smaller, identical-shaped copies of itself. Break the problem and the pieces are little versions of the whole.
• Overlapping subproblems. Those smaller questions aren’t all different. The same junction — the same subproblem — gets reached again and again from different directions. That repetition is the opening dynamic programming exists to exploit.

When both are true, the move never changes: solve each distinct subproblem once, write the answer down, reuse it forever. That’s it. That’s dynamic programming — a grand name for don’t re-walk a corridor you’ve already mapped.

Where you already meet it

Once you learn to hear "same subproblem, over and over," it’s humming under a lot of everyday software: your spell-checker ranking corrections by edit distance (the fewest insertions, deletions, and swaps to turn one word into another), a text editor choosing where to break a paragraph into justified lines, "content-aware" image resizing that carves out the least-noticeable seam, even the alignment of two DNA strands.

But the one worth slowing down on is the humble diff — the thing that tells you "3 lines added, 1 removed" on every code review. When it compares two versions of a file, it’s solving the longest common subsequence problem: the longest run of lines that appears, in order, in both files. Everything in that shared backbone is "unchanged"; everything else is an insertion or a deletion.

Why is that dynamic programming? Because the best alignment of two files is built from the best alignment of their prefixes — line up all but the last line of each and you’re left with a smaller copy of the exact same question. And those prefix-versus-prefix subproblems repeat relentlessly: comparing file A’s first 200 lines against B’s first 300 leans on A’s first 199 against B’s first 300, which leans on 199 against 299, and the same prefix pairs get revisited from many directions. Solve each (i, j) prefix pair once, store it in a grid, and a comparison that would take astronomically long by brute force finishes in a rows × columns sweep. That grid is exactly the two-dimensional table we’ll fill by hand later — diff is the knapsack’s twin.

What it actually looks like

Let’s make the repetition impossible to unsee. Take the sequence from the top — call the n-th value fib(n) — written the most natural way: each value is the sum of the two before it. Draw the calls that spawns for fib(5) and you get a tree.

Read it top-down: fib(5) needs fib(4) and fib(3); each of those splits again, all the way down to fib(1) and fib(0), the only calls that know their answer without asking anyone. Now look at the colours. The whole red subtree recomputes fib(3) — the identical work already done at the yellow node. Push n higher and this doesn’t get a little worse, it detonates: the number of calls grows like φⁿ (where φ ≈ 1.618), so fib(50) naively is billions of calls for a ten-digit answer.

The entire tree is a monument to wasted effort — and every wasted node is a subproblem we already answered somewhere else. Fix that, and we fix everything.

Let’s build one, step by step

We’ll grow it in small pieces and assemble the full class at the end.

Step 1 — write the recurrence, watch it explode

The naive version is a direct transcription of the definition. There’s nothing wrong with it except the speed.

public static long fibNaive(int n) {
    if (n < 2) {
        return n;               // base cases: fib(0)=0, fib(1)=1
    }
    return fibNaive(n - 1) + fibNaive(n - 2);
}

The rule it obeys is just the math: fib(n) = fib(n-1) + fib(n-2), stopped by the two base cases. It’s correct. It’s also the cursed you from the opening — every call re-derives a whole subtree it has no memory of. Here’s the honest cost: computing fib(n) this way makes 2·fib(n+1) − 1 calls. That count is itself a Fibonacci number, which is a poetic way of saying the work grows as fast as the thing you’re computing. That’s exponential, O(φⁿ) time. Run fibNaive(50) and go make tea.

Step 2 — remember what you solve (top-down memoization)

Now the one-line miracle. What if, the first time we compute fib(k), we write the answer in a little notebook — and before doing any work, we check the notebook first? A subproblem gets solved at most once; every later request is a lookup.

public static long fibMemo(int n) {
    long[] memo = new long[n + 1];
    Arrays.fill(memo, -1);              // -1 means "not solved yet"
    return fibMemo(n, memo);
}
 
private static long fibMemo(int n, long[] memo) {
    if (n < 2) {
        return n;
    }
    if (memo[n] != -1) {
        return memo[n];                 // already solved — just read it
    }
    return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}

This is top-down memoization: you still write the recursion exactly as the definition reads — top down, fib(n) asking for smaller values — but a cache (the memo array) intercepts the repeats. The very first fib(3) does the real work and stores 2; the second fib(3) the tree wanted is now a single array read, its whole subtree pruned away. Go back to that exploding recursion tree and mentally delete every duplicate subtree — what’s left is a thin spine of n + 1 distinct subproblems, each done once. Exponential just collapsed to O(n) time (plus O(n) for the notebook and the call stack).

Step 3 — or fill a table instead (bottom-up tabulation)

Memoization works top-down and lets the cache catch repeats as they happen. There’s a mirror-image approach that flips the direction: instead of starting at fib(n) and recursing down to the base cases, start at the base cases and build upward, filling a table in an order that guarantees every value is ready before it’s needed.

public static long fibTable(int n) {
    if (n < 2) {
        return n;
    }
    long[] dp = new long[n + 1];
    dp[0] = 0;
    dp[1] = 1;                          // seed the base cases
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];  // both inputs already filled
    }
    return dp[n];
}

This is bottom-up tabulation. No recursion, no call stack — just a loop marching left to right across dp, and because we go in increasing order, dp[i-1] and dp[i-2] are always already filled when we reach dp[i]. Same O(n) time, same answer. The two styles are two roads to one destination: memoization is the recursion you already know, taught to remember; tabulation is that same dependency order, written out as a loop.

And once it’s a plain left-to-right sweep, a second saving jumps out. To compute dp[i] you only ever glance back two cells — so why keep the whole array? Keep two variables and the space drops from O(n) to O(1):

public static long fibRolling(int n) {
    if (n < 2) {
        return n;
    }
    long prev = 0;
    long curr = 1;
    for (int i = 2; i <= n; i++) {
        long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

That "you only need the last little slice of the table" observation is the seed of a real space optimization we’ll cash in for actual money on the knapsack. Hold onto it.

Is it even a dynamic-programming problem?

Before you reach for a table, make sure the problem actually wants one — because the two ingredients from the maze are also what separate dynamic programming from its two lookalikes.

• Versus plain divide-and-conquer (like merge sort). Divide-and-conquer also builds a big answer from smaller ones, so it has optimal substructure — but its subproblems don’t overlap. Merge sort’s two halves are disjoint; nothing is ever asked twice, so there’s nothing to cache. No overlap → no DP, just recursion.
• Versus greedy. Greedy also assembles small choices into a big answer, but it commits to whatever looks best locally and never reconsiders. That works only when a locally-best choice is provably globally-best. When it isn’t — when you must weigh whole combinations against each other — greedy quietly returns a wrong answer, and you need DP to compare the sub-answers instead of gambling on one.

So the litmus test is two questions. Does the answer decompose into smaller versions of the same question? (optimal substructure — if not, DP has no grip). Do those smaller questions repeat? (overlapping subproblems — if not, plain recursion is already optimal and a cache buys nothing). Yes to both, and you memoize.

The four-part recipe

Once you’ve decided it is dynamic programming, every solution — from three-line Fibonacci to a gnarly grid problem — snaps together from the same four decisions. Get these four right and the code writes itself.

1. State — what a subproblem is: the parameters that name it. For Fibonacci that’s a single number, i. Fewer, tighter parameters mean a smaller table and a faster solution.
2. Transition — how a state’s answer is built from smaller states. Fibonacci: dp[i] = dp[i-1] + dp[i-2].
3. Base case — the smallest states you can answer outright, with no recursion. Fibonacci: dp[0] = 0, dp[1] = 1.
4. Order — the sequence to fill states so every input is ready first. Fibonacci: increasing i. (Top-down memoization figures the order out for you, on the fly, through the recursion; bottom-up, you choose it yourself.)

Naming the state is the creative leap — it’s where you decide what a subproblem even means. The other three usually fall out of it. Let’s watch all four come alive on a problem where a state needs two numbers to name it, not one.

The real test: a two-dimensional table

Here’s the classic that promotes you from one-dimensional Fibonacci to real dynamic programming. You’re a thief with a knapsack that holds at most W kilos. Each item has a weight and a value, and for each one you may take it or leave it — no fractions, no duplicates. (That’s what "0/1" means: zero or one of each.) Maximise the value you carry.

Why isn’t this just greedy? Grab the most valuable item first and you might blow your whole weight budget on it when two lighter items together were worth more. Grab the best value-per-kilo and you can still get boxed out by how the weights happen to add up. You genuinely have to weigh combinations — the exact signal for dynamic programming. Let’s turn the recipe’s crank.

State. A subproblem here needs two facts, not one: which items you’re allowed to consider, and how much capacity is left. So let dp[i][c] be the best value using only the first i items within a capacity of c. Two parameters → a two-dimensional table.

Transition. Stand at item i with capacity c and you face exactly one yes/no question — take it or skip it:

• Skip it: you get whatever the best was with one fewer item, same capacity — dp[i-1][c].
• Take it (only if it fits, weight[i] ≤ c): its value, plus the best you could do with the remaining capacity and one fewer item — value[i] + dp[i-1][c - weight[i]].
• dp[i][c] is the larger of the two.

Read the picture. To fill the yellow cell we look only at the row above — the world with one fewer item to worry about. Straight up is the skip answer: same capacity, one fewer item. Up and to the left by exactly this item’s weight is the take answer: we spent weight[i] kilos, so we consult the best we could’ve managed with the capacity that’s left, then add the item’s value. The cell is the better of those two. Every single cell in the grid is that same little max.

Base case. With zero items considered (i = 0) you can carry nothing, so dp[0][c] = 0 for every capacity — the whole top row is zeros. That row is the floor every other cell eventually stands on.

Order. A cell only ever reads from the row directly above it, so fill item by item, top row downward, sweeping every capacity within a row. By the time you compute row i, row i-1 is complete. The answer lands in the bottom-right corner, dp[n][W].

public static int knapsack(int[] weight, int[] value, int capacity) {
    int n = weight.length;
    int[][] dp = new int[n + 1][capacity + 1];
    for (int i = 1; i <= n; i++) {
        for (int c = 0; c <= capacity; c++) {
            dp[i][c] = dp[i - 1][c];                    // skip item i
            if (weight[i - 1] <= c) {                   // does it fit?
                int take = value[i - 1] + dp[i - 1][c - weight[i - 1]];
                dp[i][c] = Math.max(dp[i][c], take);    // better of skip / take
            }
        }
    }
    return dp[n][capacity];
}

Run it on the three items from the diagram — weights 1, 2, 3 with values 2, 4, 7 and a capacity of 5 — and the bottom-right corner comes out 11: the thief takes the weight-2 and weight-3 items (exactly 5 kilos) for 4 + 7. The table is n × W cells, each filled in O(1), so it’s O(n · W) time and O(n · W) space.

Shrinking the table to one row

That O(n · W) space is the next thing to attack, and it hides the single sneakiest trap in all of introductory dynamic programming. Notice that row i only ever reads from row i-1 — never from i-2, never from itself. So why keep all n rows? Keep one row and overwrite it in place as each item arrives.

But now the direction of the sweep matters enormously, and getting it backwards is the most common knapsack bug there is.

When we collapse to a single dp[], computing dp[c] needs the old dp[c - weight] — the value from before this item was considered. Sweep capacities left to right and, by the time you reach dp[c], the cell dp[c - weight] has already been updated for the current item. You’d be quietly allowing the same item to be picked up twice in one pass — which solves the unbounded knapsack (unlimited copies of each item), not the 0/1 one you were asked for. Right answer to the wrong problem.

The fix is one character: sweep capacities right to left, from W down to weight[i]. Now when you write dp[c], the cell dp[c - weight] to its left still holds the previous item’s value, because this pass hasn’t reached it yet. Each item gets considered exactly once.

public static int knapsackRolling(int[] weight, int[] value, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int c = capacity; c >= weight[i]; c--) {   // right to left!
            dp[c] = Math.max(dp[c], value[i] + dp[c - weight[i]]);
        }
    }
    return dp[capacity];
}

Same answer, 11, in the same O(n · W) time but now only O(W) space — one row instead of the whole grid. That right-to-left sweep is a genuine "you know it or you don’t" detail; interviewers use it precisely to tell whether you understand why the table works or just memorised its shape.

Memoization vs tabulation vs brute force

The problem all three attack is the same recurrence; they differ in how they avoid the repeated work — or, for brute force, fail to. Call the number of distinct subproblems the number of states.

Same asymptotic time for both DP styles — the choice is about temperament and constraints. Memoization is the recurrence you already wrote, plus a cache; it only ever computes the states it actually reaches, which is a real win when the reachable states are a sparse slice of the whole space (reach for a HashMap cache then). Its risk is the call stack — a recursion n levels deep can overflow. Tabulation has no stack and unlocks the rolling-array space cut you just saw, but it computes every state whether needed or not, and it makes you get the fill order right by hand.

The complete implementation

Everything above, assembled — Fibonacci four ways and the 0/1 knapsack in both its full-grid and one-row forms:

package dev.fiveyear.dp;
 
import java.util.Arrays;
 
public final class DynamicProgramming {
 
    private DynamicProgramming() {}
 
    /** Naive recurrence — correct, but O(φⁿ) calls of pure repeated work. */
    public static long fibNaive(int n) {
        if (n < 2) {
            return n;
        }
        return fibNaive(n - 1) + fibNaive(n - 2);
    }
 
    /** Top-down memoization: each fib(k) is solved once, then cached. O(n). */
    public static long fibMemo(int n) {
        long[] memo = new long[n + 1];
        Arrays.fill(memo, -1);
        return fibMemo(n, memo);
    }
 
    private static long fibMemo(int n, long[] memo) {
        if (n < 2) {
            return n;
        }
        if (memo[n] != -1) {
            return memo[n];                 // already solved — just read it
        }
        return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    }
 
    /** Bottom-up tabulation: fill dp[0..n] in order. O(n) time, O(n) space. */
    public static long fibTable(int n) {
        if (n < 2) {
            return n;
        }
        long[] dp = new long[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];  // both inputs already filled
        }
        return dp[n];
    }
 
    /** Only the last two values are ever needed → O(1) space. */
    public static long fibRolling(int n) {
        if (n < 2) {
            return n;
        }
        long prev = 0;
        long curr = 1;
        for (int i = 2; i <= n; i++) {
            long next = prev + curr;
            prev = curr;
            curr = next;
        }
        return curr;
    }
 
    /** 0/1 knapsack: best value within capacity, each item used at most once. */
    public static int knapsack(int[] weight, int[] value, int capacity) {
        int n = weight.length;
        int[][] dp = new int[n + 1][capacity + 1];
        for (int i = 1; i <= n; i++) {
            for (int c = 0; c <= capacity; c++) {
                dp[i][c] = dp[i - 1][c];                    // skip item i
                if (weight[i - 1] <= c) {                   // does it fit?
                    int take = value[i - 1] + dp[i - 1][c - weight[i - 1]];
                    dp[i][c] = Math.max(dp[i][c], take);    // better of skip / take
                }
            }
        }
        return dp[n][capacity];
    }
 
    /** Same answer in O(capacity) space — sweep capacity high → low. */
    public static int knapsackRolling(int[] weight, int[] value, int capacity) {
        int[] dp = new int[capacity + 1];
        for (int i = 0; i < weight.length; i++) {
            for (int c = capacity; c >= weight[i]; c--) {   // right to left!
                dp[c] = Math.max(dp[c], value[i] + dp[c - weight[i]]);
            }
        }
        return dp[capacity];
    }
}

And here it is producing exactly the outputs the comments claim:

DynamicProgramming.fibNaive(10);     // 55
DynamicProgramming.fibMemo(50);      // 12586269025
DynamicProgramming.fibTable(50);     // 12586269025
DynamicProgramming.fibRolling(90);   // 2880067194370816120  (largest that fits in long-ish)
 
int[] weight = {1, 2, 3};
int[] value  = {2, 4, 7};
DynamicProgramming.knapsack(weight, value, 5);         // 11  → take the weight-2 and weight-3 items
DynamicProgramming.knapsackRolling(weight, value, 5);  // 11  → same answer, a single row

The four Fibonacci variants agree on every input; the two knapsacks agree on every capacity. The naive one is there only to be outrun.

The interview corner

Dynamic programming is the topic candidates dread most, which is exactly why walking in with a system beats "remembering" any single problem. The interviewer isn’t testing whether you’ve seen this exact question — they’re testing whether you can find the state.

Ask these before you write a line:

• "Do the subproblems actually overlap, or is each one distinct?" If nothing repeats, this is plain divide-and-conquer and a cache buys nothing. Establishing overlap is what justifies DP at all.
• "What’s the range of every parameter — especially any capacity, budget, or target sum?" The table is sized by those ranges. A capacity of 50 is a tiny grid; a capacity of two billion means O(n · W) is a trap and you need another idea. This decides feasibility.
• "Do you want the optimum’s _value, or the actual choices that achieve it?"_ Reconstructing which items were taken needs the full table (or parent pointers) — the moment you say "and give me the items," the O(W) rolling trick is off the table.

The follow-up ladder — where a strong candidate keeps climbing:

1. "Now tell me which items were taken." Walk the full 2-D table backward from dp[n][W]: if dp[i][c] differs from dp[i-1][c], item i was taken — record it, subtract its weight, and continue up. Reconstruction is why you sometimes keep the whole grid.
2. "Items can now be taken unlimited times (unbounded knapsack)." Same recurrence, but the take branch reads the current row (dp[i][c-w]), and the one-row sweep runs left to right — the very "bug" from earlier is now the feature.
3. "The recursion is 100,000 deep and memoization stack-overflows." Convert to bottom-up tabulation: it lives on the heap with an explicit loop and no call stack, so depth stops mattering.
4. "The state space is astronomically large but most of it is never reached." Prefer top-down memoization with a HashMap keyed by the state — it materialises only the subproblems you actually visit, instead of allocating a giant mostly-empty table.
5. "Instead of maximising, count the ways (or minimise the maximum)." Same table machinery; just swap the transition’s combinator — max becomes + for counting, or min for a minimax. The skeleton is identical, which is the whole point. (It’s the same "define the monotonic thing you’re optimising" instinct behind binary search on the answer.)

Three mistakes that fail the round:

• Sweeping the one-row knapsack left to right. It silently solves the unbounded version — a correct-looking answer to a different problem, the worst kind of wrong because small tests pass.
• A cache that never gets read. Writing to memo but forgetting to check it first (or checking after you’ve already recursed) is the exponential version wearing a costume. The read has to come before the work.
• A botched base case or fill order. Seeding the wrong base row, or filling in an order where a cell reads a neighbour that isn’t computed yet, returns 0 or garbage on the edges — passing the friendly cases and failing the adversarial one they hand you on purpose.

Where to go from here

You now own the core: spot optimal substructure and overlapping subproblems, name the state, write the transition and base case, then either memoize top-down or tabulate bottom-up — and shrink the table when a row only reads the row before it. Three natural next stops:

• The DP zoo, one state at a time. Longest common subsequence and edit distance (the diff twins), coin change, longest increasing subsequence, matrix-chain multiplication — each is just "name the state, write the transition." Once you’ve done five, the sixth is pattern recognition.
• DP on other shapes. The same "solve subproblems in dependency order" idea runs on trees (subtree states) and on directed acyclic graphs (where shortest path is a dynamic program) — and connects to the merge-and-query world of union-find and the one-pass discipline of the sliding window, the other two ideas that carry most interview rounds.
• When memory is the wall. The rolling-array trick generalises: many 2-D DPs keep only the last row or two, and bitmask DP packs an entire subset into a single integer of state.

Next time a code review says "3 lines changed," you’ll know a little grid quietly lined up the two files and found their longest shared backbone — and next time you rattle off the Fibonacci sequence, you’ll know the only reason it’s easy is that you, unlike the cursed version, remember.