Dynamic Programming Basics

The problem: naive recursion repeats itself

The Fibonacci sequence starts 0, 1, and every number after is the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, 13. The definition is recursive (fib(n) = fib(n-1) + fib(n-2)) so the direct translation into code is two recursive calls and a base case.

Now trace fib(5). It calls fib(4) and fib(3). But fib(4) also calls fib(3). Both of those call fib(2), which gets computed three separate times, and fib(1) five times. The call tree doubles roughly every level, so the running time is exponential, about O(2^n). fib(50) at that rate is over a trillion calls. Minutes to hours of compute for a number you could work out on paper.

The wasted work has a name: overlapping subproblems. The recursion keeps arriving at the same question. What is fib(3)?. Through different paths, and dumbly recomputes it every time. The answer never changes. This is the exact situation DP exists to fix.

static long fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

Memoization: top-down DP

Memoization (no r. Think memo, as in a note) is the smallest possible fix: before computing, check your notes; after computing, write the result down. Keep an array or HashMap keyed by the input. Each call first asks, have I solved fib(n) before? If yes, return the stored answer in O(1). If no, compute it the normal recursive way, store it, then return it.

This is called top-down because you still start from the big problem (fib(50)) and recurse downward; the cache just short-circuits repeats. Every distinct subproblem is now computed exactly once (there are only n + 1 of them) so the running time collapses from O(2^n) to O(n). fib(50) drops from a trillion calls to about a hundred.

The beauty of memoization is how mechanical it is: take any correct recursive solution whose answers depend only on the arguments, add a cache lookup at the top and a cache store before the return, and you are done. The recursive structure, base cases, and reasoning all stay identical.

static long[] memo = new long[51];

static long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

Tabulation: bottom-up DP

Tabulation reaches the same destination from the opposite direction. Instead of starting at fib(n) and recursing down, start at the smallest answers and build a table upward: fill in fib(0) and fib(1) directly, then compute fib(2) from them, then fib(3), looping until the table reaches n. No recursion at all, just an array and a for loop.

Each table entry is computed once from entries already filled in, so time is O(n) again, but tabulation has two extra perks. First, no call stack, so no risk of StackOverflowError on large inputs. Second, it exposes space optimizations: to fill entry i you only ever read entries i-1 and i-2, so you can throw away the rest of the table and keep just two variables, cutting space from O(n) to O(1).

Top-down or bottom-up is mostly taste. Memoization is easier to write because it follows the recursion you already found; tabulation is usually a bit faster and safer on deep inputs. In interviews, a common path is: derive the recursive relation, memoize it, then convert to a table if time permits.

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

How to spot a DP problem

Two properties must hold. Overlapping subproblems: the naive recursion revisits the same states many times (unlike, say, merge sort, whose subproblems never repeat, that is divide and conquer, not DP). Optimal substructure: the best answer to the big problem can be assembled from best answers to smaller ones. Fibonacci trivially has both; so do most counting and optimization problems on sequences.

The problem statements give off recognizable signals. Phrases like count the number of ways, minimum cost, maximum profit, or longest subsequence (combined with choices at each step) usually mean DP. Classic first problems: Climbing Stairs (count ways to reach step n, which is Fibonacci in disguise), House Robber (max loot when adjacent houses cannot both be robbed), and Coin Change (fewest coins to make an amount).

A practical recipe for any of them: define the state in words (dp[i] is the best answer for the first i items), find the recurrence (how dp[i] follows from earlier entries), set base cases, and choose memoization or tabulation. The recurrence is the creative step and the rest is mechanical. DP tells you the best value achievable, and its natural rival is the greedy strategy, which tries to skip the table entirely by committing to the best-looking choice at each step. When that shortcut is safe, and when it quietly fails, is the next lesson.

Frequently asked