Dynamic Programming

Dynamic programming is one idea: solve each subproblem once and remember the answer. The name is famously unhelpful — it was chosen in the 1950s to sound impressive to a funding committee — and it puts people off something that is genuinely simple.

When it applies

Two conditions, and both must hold.

1. Overlapping subproblems — the same subproblem is solved again and again.
2. Optimal substructure — the best answer is built from best answers to smaller versions.

Without overlap, caching is pure overhead — which is precisely why merge sort is divide and conquer and not DP. Without optimal substructure, combining sub-answers gives the wrong result.

The example that makes the case

The naive recursive Fibonacci is O(2ⁿ) because it recomputes the same values astronomically often — fib(30) alone is evaluated over a million times on the way to fib(50).

Bottom-up, it is O(n) time and O(1) space:

    public static long fibonacci(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("negative index");
        }
        if (n < 2) {
            return n;
        }
        long previous = 0;
        long current = 1;
        for (int i = 2; i <= n; i++) {
            long next = previous + current;
            previous = current;
            current = next;
        }
        return current;
    }

        Check.eq(fibonacci(50), 12586269025L, "fib(50) - instant, unlike the naive version");
        Check.eq(fibonacci(90), 2880067194370816120L, "fib(90) still fits in a long");

From "longer than a lunch break" to instant, by keeping two numbers. Note the general DP table would be O(n) space; this recurrence only ever looks back two steps, so it needs two variables. Recognising that is a common follow-up question.

Two ways to write it

Top-down (memoisation) — the natural recursion, plus a cache:

    private static long fibMemo(int n, long[] cache, boolean[] known) {
        if (n < 2) {
            return n;
        }
        if (known[n]) {
            return cache[n];
        }
        known[n] = true;
        return cache[n] = fibMemo(n - 1, cache, known) + fibMemo(n - 2, cache, known);
    }

Bottom-up (tabulation) — fill a table in order, no recursion at all. That is the loop above.

Write it top-down first, because it follows directly from the recursive definition. Convert to bottom-up if the depth is a problem or you want to shrink the table.

The separate known[] array is deliberate: cache[n] == 0 cannot distinguish "not computed yet" from "the answer is genuinely 0". Using a sentinel value that is also a legal answer is a classic memoisation bug.

Coin change — where greedy fails

    public static int coinChange(int[] coins, int amount) {
        int impossible = amount + 1;                  // larger than any real answer
        int[] best = new int[amount + 1];
        Arrays.fill(best, impossible);
        best[0] = 0;                                  // zero coins make zero

        for (int value = 1; value <= amount; value++) {
            for (int coin : coins) {
                if (coin <= value && best[value - coin] + 1 < best[value]) {
                    best[value] = best[value - coin] + 1;
                }
            }
        }
        return best[amount] >= impossible ? -1 : best[amount];
    }

Read the structure: best[value] is the fewest coins making value, built from best of smaller values. That is optimal substructure written out.

The sentinel is amount + 1 rather than Integer.MAX_VALUE deliberately — adding 1 to MAX_VALUE overflows to a large negative number, which then looks like an extremely good answer. A sentinel you might add to has to leave headroom.

And the payoff, checked against the greedy version in the same test suite:

        Check.eq(coinChange(new int[] {1, 3, 4}, 6), 2, "3+3 beats greedy's 4+1+1");
        Check.eq(coinChange(new int[] {2}, 3), -1, "cannot be made");

Two dimensions

Longest common subsequence — the table is a grid, and each cell depends on three neighbours:

    public static int longestCommonSubsequence(String a, String b) {
        int[][] table = new int[a.length() + 1][b.length() + 1];
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                table[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
                        ? table[i - 1][j - 1] + 1
                        : Math.max(table[i - 1][j], table[i][j - 1]);
            }
        }
        return table[a.length()][b.length()];
    }

The extra row and column of zeroes are what remove every special case for an empty prefix — worth the memory, every time.

⚠️ Knapsack, and a loop direction that changes the problem

    public static int knapsack(int[] weights, int[] values, int capacity) {
        int[] best = new int[capacity + 1];
        for (int i = 0; i < weights.length; i++) {
            // DOWNWARDS. Ascending would let one item be taken twice, which is the unbounded
            // knapsack - a different problem with a different answer.
            for (int c = capacity; c >= weights[i]; c--) {
                best[c] = Math.max(best[c], best[c - weights[i]] + values[i]);
            }
        }
        return best[capacity];
    }

This is the subtlest thing in the post. Iterating capacity downwards means best[c - weights[i]] still holds the value from before this item was considered, so the item is used at most once. Iterate upwards and it reads a value that already includes this item — which solves the unbounded knapsack, where items may be taken repeatedly.

Both are one-character changes, both compile, and both return plausible numbers. Only one answers the question you asked.

Kadane's algorithm

Largest sum of any contiguous subarray, in one pass:

        int best = a[0];
        int endingHere = a[0];
        for (int i = 1; i < a.length; i++) {
            // Either extend the run, or start again at this element.
            endingHere = Math.max(a[i], endingHere + a[i]);
            best = Math.max(best, endingHere);
        }
        return best;

DP with a table of two variables. Starting both at a[0] rather than 0 is what makes an all-negative array return its largest element instead of 0 — a real distinction, and one the tests pin down:

        Check.eq(maxSubarraySum(new int[] {-5, -2, -9}), -2, "all negative returns the largest");

How to approach a DP problem

1. Write the recursion first, ignoring efficiency. If it is correct and slow, you are most of the way there.
2. Name the state. What arguments actually distinguish one subproblem from another? That is your table's dimensions.
3. Add a cache. You now have a working top-down solution.
4. Convert to a table if you need to, filling in dependency order.
5. Shrink it if only the last row or two is ever read.

Step 2 is the one that decides everything. Get the state wrong and no amount of caching helps — two different subproblems collide on one cache entry and the answers are simply wrong.

What to remember

• Solve each subproblem once, remember the answer.
• Needs overlapping subproblems and optimal substructure.
• Top-down is easier to derive; bottom-up cannot overflow the stack.
• Sentinels must leave headroom — MAX_VALUE + 1 is negative.
• Knapsack's loop direction decides which problem you are solving.
• Getting the state right matters more than the caching.