Dynamic Programming: Learn to Recognize Overlapping Subproblems

If you add up 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 you get 8. If someone then says "and one more?", you do not start counting again from the first 1. You remember that the total so far is 8, and say 9.

That is the whole idea of dynamic programming (DP): do not solve the same small problem twice; remember the answer and reuse it. DP has a reputation for being hard, and mostly that is because it is often taught as a list of problems to memorise. This article teaches it as a method instead. By the end you will have a six-step routine that you can apply to a problem you have never seen.

• The two properties that make a problem suitable for DP.
• How memoization and tabulation work, using Fibonacci as the smallest example.
• A six-step workflow for formulating a DP solution.
• How to solve the minimum-coin-change problem top-down and bottom-up.
• How to recognise a DP problem, and the usual mistakes.

A problem is a good candidate for DP when it has both of these.

1. Overlapping subproblems. A plain recursive solution ends up solving the same subproblem again and again. (If every subproblem is different, like in merge sort, there is nothing to reuse, and that is divide and conquer, not DP.)
2. Optimal substructure. The best answer to the big problem can be built from the best answers to smaller versions of the same problem.

In the recursion article you drew the tree for fib(4) and saw fib(2) computed twice. That repetition is what DP removes.

The Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, ..., where each is the sum of the two before it: fib(n) = fib(n - 1) + fib(n - 2), with fib(0) = 0 and fib(1) = 1.

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

This is correct but explosive. fib(n) calls fib(n - 1) and fib(n - 2), and those overlap heavily: fib(n - 2) is computed inside both. The number of calls roughly multiplies by 1.6 each time n grows by one. For n = 30 it makes 2.7 million calls, and n = 50 would take billions.

Memoization keeps the recursion but adds a cache. Before computing fib(n), look it up. If it has been computed, return it. Otherwise compute it, store it, and return it. Now each value is computed once, and every other request is a quick look-up.

Tabulation removes the recursion. You decide the order in which subproblems must be solved (smallest first) and fill a table in that order. For Fibonacci: dp[0] = 0, dp[1] = 1, and dp[i] = dp[i - 1] + dp[i - 2] for i from 2 to n.

dp[i] only needs the previous two values. So we do not need the whole table. Two variables are enough. The time stays O(n) and the space drops from O(n) to O(1).

// File: Main.javaimport java.util.Arrays;public class Main {    static long naiveCalls = 0;    static long memoCalls = 0;    static long fibNaive(int n) {        naiveCalls++;        if (n <= 1) {            return n;        }        return fibNaive(n - 1) + fibNaive(n - 2);    }    static long fibMemo(int n, long[] memo) {        memoCalls++;        if (n <= 1) {            return n;        }        if (memo[n] != -1) {            return memo[n];                           // already computed: reuse it        }        memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);        return memo[n];    }    static long fibTable(int n) {        if (n <= 1) {            return n;        }        long[] dp = new long[n + 1];        dp[1] = 1;        for (int i = 2; i <= n; i++) {            dp[i] = dp[i - 1] + dp[i - 2];        }        return dp[n];    }    static long fibConstantSpace(int n) {        if (n <= 1) {            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;    }    public static void main(String[] args) {        int n = 30;        long[] memo = new long[n + 1];        Arrays.fill(memo, -1);                        // -1 means "not computed yet"        long a = fibNaive(n);        long b = fibMemo(n, memo);        System.out.println("fib(30) naive: " + a + " with " + naiveCalls + " calls");        System.out.println("fib(30) memo:  " + b + " with " + memoCalls + " calls");        System.out.println(fibTable(n) + " " + fibConstantSpace(n));        long[] bigMemo = new long[51];        Arrays.fill(bigMemo, -1);        System.out.println("fib(50) = " + fibMemo(50, bigMemo));        System.out.println("fib(92) = " + fibConstantSpace(92));        System.out.println("fib(93) = " + fibConstantSpace(93) + "  (overflowed a long)");    }}

fib(30) naive: 832040 with 2692537 callsfib(30) memo:  832040 with 59 calls832040 832040fib(50) = 12586269025fib(92) = 7540113804746346429fib(93) = -6246583658587674878  (overflowed a long)

The naive version made about 2.7 million calls for n = 30, and the memoised version made only 59. The ratio keeps growing with n. The last two lines carry a warning that is easy to forget: Fibonacci numbers grow so fast that long overflows at fib(93), and Java does not tell you. For larger values use BigInteger, or the modulo trick from the previous article.

A good strategy when you are learning: write the plain recursive solution first (that is your state and transition), then add a memo to get a working DP, and only then convert to a table if you want the speed or space savings.

Almost every DP solution can be built with these six steps. Write the answer to each in a comment before you code.

1. Define the state. What does one table entry mean? Write it as a precise sentence. Example: "dp[a] is the fewest coins needed to make the amount a." A vague state is the root of most DP failures.
2. Write the transition. How does dp[i] depend on smaller states? This is the heart of the solution. Example: dp[a] = 1 + min(dp[a - c]) over all coins c.
3. Set the base cases. The smallest states that need no recursion. Example: dp[0] = 0.
4. Fix the evaluation order. Make sure each state is computed after the states it depends on. For dp[a] depending on smaller amounts, go from small to large.
5. Name the answer. Which entry (or entries) holds the final answer? Example: dp[amount].
6. Count the cost. Time is the number of states × the work per state. Space is the number of states, or fewer if you can drop old ones.

Then check by hand on a small example, and (if possible) compare with a slow brute force on small inputs.

Problem. You have coins of certain denominations (an unlimited supply of each) and a target amount. Find the fewest coins that make exactly that amount, or -1 if it is impossible. For coins {1, 3, 4} and amount 6, the answer is 2 (3 + 3).

Remember from the greedy article that grabbing the biggest coin first gives 4 + 1 + 1, which is three coins. Greedy fails. DP does not guess: for every amount, it tries every coin.

Run the six steps:

1. State. dp[a] = the fewest coins to make amount a, or "impossible".
2. Transition. To make a, the last coin could be any coin c with c <= a. If we use it, the rest is a - c, which needs dp[a - c] coins, plus one for c. So dp[a] = 1 + min(dp[a - c]) over all coins c <= a where a - c is possible.
3. Base case. dp[0] = 0: zero coins make amount zero.
4. Order. a from 1 up to amount, since dp[a] uses smaller amounts.
5. Answer. dp[amount], or -1 if it is impossible.
6. Cost. There are amount + 1 states, each tries every coin: O(amount × number of coins) time, O(amount) space.

"Impossible" needs a value. A common trick is to fill the table with amount + 1, which is larger than any real answer (you never need more than amount coins, if the smallest coin is 1). It avoids overflow, which we get wrong in an exercise below.

Dry run for coins {1, 3, 4} and amount 6:

So dp[6] = 2, with the best last coin being 3 (leaving dp[3] = 1, another 3). To recover which coins were used, remember for each amount which coin gave the minimum, then walk back from the amount.

The memoised version below uses the same recurrence, written as a recursive function. Its cache holds -2 for "not computed", -1 for "impossible", and a non-negative number otherwise.

// File: Main.javaimport java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Main {    // Bottom-up. O(amount * coins) time, O(amount) space.    static int minCoinsTable(int[] coins, int amount) {        int[] dp = new int[amount + 1];        Arrays.fill(dp, amount + 1);                     // amount + 1 stands for "impossible"        dp[0] = 0;        for (int a = 1; a <= amount; a++) {            for (int coin : coins) {                if (coin <= a) {                    dp[a] = Math.min(dp[a], dp[a - coin] + 1);                }            }        }        return dp[amount] > amount ? -1 : dp[amount];    }    // Top-down. memo[a]: -2 not computed, -1 impossible, otherwise the fewest coins.    static int minCoinsMemo(int[] coins, int amount, int[] memo) {        if (amount == 0) {            return 0;        }        if (amount < 0) {            return -1;        }        if (memo[amount] != -2) {            return memo[amount];        }        int best = -1;        for (int coin : coins) {            int sub = minCoinsMemo(coins, amount - coin, memo);            if (sub >= 0 && (best == -1 || sub + 1 < best)) {                best = sub + 1;            }        }        memo[amount] = best;        return best;    }    // Plain recursion with no cache: only for tiny inputs, as a reference.    static int minCoinsBrute(int[] coins, int amount) {        if (amount == 0) {            return 0;        }        int best = -1;        for (int coin : coins) {            if (coin <= amount) {                int sub = minCoinsBrute(coins, amount - coin);                if (sub >= 0 && (best == -1 || sub + 1 < best)) {                    best = sub + 1;                }            }        }        return best;    }    // Rebuilds one optimal list of coins.    static List<Integer> coinsUsed(int[] coins, int amount) {        int[] dp = new int[amount + 1];        int[] lastCoin = new int[amount + 1];        Arrays.fill(dp, amount + 1);        dp[0] = 0;        for (int a = 1; a <= amount; a++) {            for (int coin : coins) {                if (coin <= a && dp[a - coin] + 1 < dp[a]) {                    dp[a] = dp[a - coin] + 1;                    lastCoin[a] = coin;                    // remember the choice that gave the best value                }            }        }        List<Integer> used = new ArrayList<>();        if (dp[amount] > amount) {            return used;                                   // impossible: empty list        }        for (int a = amount; a > 0; a -= lastCoin[a]) {            used.add(lastCoin[a]);        }        return used;    }    static int viaMemo(int[] coins, int amount) {        int[] memo = new int[amount + 1];        Arrays.fill(memo, -2);        return minCoinsMemo(coins, amount, memo);    }    public static void main(String[] args) {        int[][] coinSets = {{1, 3, 4}, {2}, {1}, {2, 5, 10, 1}, {186, 419, 83, 408}};        int[] amounts = {6, 3, 0, 27, 6249};        for (int t = 0; t < coinSets.length; t++) {            System.out.println("coins " + Arrays.toString(coinSets[t]) + " amount " + amounts[t] + ": table=" + minCoinsTable(coinSets[t], amounts[t])                    + " memo=" + viaMemo(coinSets[t], amounts[t]) + (amounts[t] <= 30 ? " brute=" + minCoinsBrute(coinSets[t], amounts[t]) : ""));        }        System.out.println(coinsUsed(new int[] {1, 3, 4}, 6) + " " + coinsUsed(new int[] {2, 5, 10, 1}, 27) + " " + coinsUsed(new int[] {2}, 3));    }}

coins [1, 3, 4] amount 6: table=2 memo=2 brute=2coins [2] amount 3: table=-1 memo=-1 brute=-1coins [1] amount 0: table=0 memo=0 brute=0coins [2, 5, 10, 1] amount 27: table=4 memo=4 brute=4coins [186, 419, 83, 408] amount 6249: table=20 memo=20[3, 3] [2, 5, 10, 10] []

All three methods agree wherever the slow brute force can finish. For {1, 3, 4} and 6, the result is 2, via [3, 3], which is the case greedy gets wrong. The last list is empty because 3 cannot be made from 2s.

Complexity: both DP versions are O(amount × coins) time and O(amount) space. Notice the number amount appears in the running time. If the amount has 12 digits, that is a trillion states. The running time is polynomial in the value of the number, not in its length. This is called pseudo-polynomial time, and it explains why DP is not a universal cure.

Signals in the problem statement:

• It asks for a minimum, maximum, count of ways, or "is it possible?"
• At each step you have a choice (take or skip, which coin, which direction).
• A brute-force recursion looks natural, but you can see the same sub-situation arising along different branches.
• The "state" is small: an index, an amount, a pair of indexes. If describing the state needs a whole list of items, it might not be DP.
• The input sizes suggest a polynomial algorithm: n up to about 10^3 or 10^4 for O(n^2), up to 10^5 or more for O(n).

A quick check: draw the recursion tree for a small input. If you see the same call with the same arguments appear twice, DP applies.

DP versus the other tools:

• A vague state definition. If you cannot say in one sentence what dp[i] means, stop and rewrite it.
• Missing or wrong base cases. dp[0] for coin change, dp[0] and dp[1] for Fibonacci.
• Wrong evaluation order, so a state reads an entry that has not been computed yet.
• Overflow with "infinity". Using Integer.MAX_VALUE and then adding 1 wraps to a negative number, which looks like the best answer. Use amount + 1, or check before adding.
• A memo sentinel that is also a valid answer. If 0 can be a real result, do not use 0 to mean "not computed". Use -1 or a separate boolean[].
• Not distinguishing "impossible" from "zero". Coin change needs three kinds of value: unknown, impossible, and a real count.
• Deep recursion. Top-down on large n may overflow the stack. Use tabulation.
• Counting versus optimising. For "number of ways" you add the options. For "minimum" you take the minimum. Mixing them is a frequent error.
• Order of loops in counting problems. Combinations (order does not matter) and permutations (order matters) differ only in which loop is on the outside, as one exercise shows.
• Shared mutable state between test cases, such as a static memo that is never reset.

static int coinChangeBuggy(int[] coins, int amount) {    int[] dp = new int[amount + 1];    Arrays.fill(dp, Integer.MAX_VALUE);    dp[0] = 0;    for (int a = 1; a <= amount; a++) {        for (int coin : coins) {            if (coin <= a) {                dp[a] = Math.min(dp[a], dp[a - coin] + 1);            }        }    }    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];}

// File: Main.javaimport java.util.Arrays;public class Main {    public static void main(String[] args) {        int[] coins = {1, 2, 5};        int amount = 7;        int[] dp = new int[amount + 1];        Arrays.fill(dp, amount + 1);        dp[0] = 0;        for (int a = 1; a <= amount; a++) {            for (int coin : coins) {                if (coin <= a) {                    dp[a] = Math.min(dp[a], dp[a - coin] + 1);                }            }        }        System.out.println(Arrays.toString(dp));    }}

[0, 1, 1, 2, 2, 1, 2, 2]

// File: Main.javapublic class Main {    static int minCostClimbingStairs(int[] cost) {        int n = cost.length;        int twoBack = 0;                   // dp[i - 2]        int oneBack = 0;                   // dp[i - 1]        for (int i = 2; i <= n; i++) {            int current = Math.min(oneBack + cost[i - 1], twoBack + cost[i - 2]);            twoBack = oneBack;            oneBack = current;        }        return oneBack;    }    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}));        System.out.println(minCostClimbingStairs(new int[] {5, 3}));        System.out.println(minCostClimbingStairs(new int[] {7}));    }}

15630

// File: Main.javapublic class Main {    static long combinations(int[] coins, int amount) {        long[] ways = new long[amount + 1];        ways[0] = 1;        for (int coin : coins) {                   // coins outside: each coin is used in a fixed order            for (int a = coin; a <= amount; a++) {                ways[a] += ways[a - coin];            }        }        return ways[amount];    }    static long sequences(int[] coins, int amount) {        long[] ways = new long[amount + 1];        ways[0] = 1;        for (int a = 1; a <= amount; a++) {        // amounts outside: any coin can be the last one            for (int coin : coins) {                if (coin <= a) {                    ways[a] += ways[a - coin];                }            }        }        return ways[amount];    }    public static void main(String[] args) {        System.out.println(combinations(new int[] {1, 2, 5}, 5) + " " + sequences(new int[] {1, 2, 5}, 5));        System.out.println(combinations(new int[] {2}, 3) + " " + combinations(new int[] {10}, 10) + " " + combinations(new int[] {1, 2, 5}, 0));    }}

4 90 1 1

// File: Main.javaimport java.util.Arrays;public class Main {    static int coinChangeBuggy(int[] coins, int amount) {        int[] dp = new int[amount + 1];        Arrays.fill(dp, Integer.MAX_VALUE);        dp[0] = 0;        for (int a = 1; a <= amount; a++) {            for (int coin : coins) {                if (coin <= a) {                    dp[a] = Math.min(dp[a], dp[a - coin] + 1);                }            }        }        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];    }    static int coinChangeFixed(int[] coins, int amount) {        int[] dp = new int[amount + 1];        Arrays.fill(dp, Integer.MAX_VALUE);        dp[0] = 0;        for (int a = 1; a <= amount; a++) {            for (int coin : coins) {                if (coin <= a && dp[a - coin] != Integer.MAX_VALUE) {      // skip impossible sub-amounts                    dp[a] = Math.min(dp[a], dp[a - coin] + 1);                }            }        }        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];    }    public static void main(String[] args) {        System.out.println(coinChangeBuggy(new int[] {2}, 3) + " " + coinChangeFixed(new int[] {2}, 3));        System.out.println(coinChangeBuggy(new int[] {1, 3, 4}, 6) + " " + coinChangeFixed(new int[] {1, 3, 4}, 6));    }}

-2147483648 -12 2

// File: Main.javaimport java.util.Arrays;public class Main {    static int numSquares(int n) {        int[] dp = new int[n + 1];        Arrays.fill(dp, Integer.MAX_VALUE);        dp[0] = 0;        for (int i = 1; i <= n; i++) {            for (int s = 1; s * s <= i; s++) {                dp[i] = Math.min(dp[i], dp[i - s * s] + 1);            }        }        return dp[n];    }    public static void main(String[] args) {        System.out.println(numSquares(12) + " " + numSquares(13) + " " + numSquares(1) + " " + numSquares(0) + " " + numSquares(7));        int worst = 0;        for (int i = 0; i <= 2000; i++) {            worst = Math.max(worst, numSquares(i));        }        System.out.println("most squares ever needed for 0..2000: " + worst);    }}

3 2 1 0 4most squares ever needed for 0..2000: 4

• Next: Dynamic Programming Practice: From 1D to 2D applies the six steps to climbing stairs, house robber, grid paths and the longest common subsequence.
• Looking back: the maximum-subarray solution in Arrays was already a tiny DP: its state was "best sum of a subarray ending at i".
• Practice habit: for every DP problem, write the six steps as comments before writing code. When a solution is wrong, the bug is almost always in the state definition or the base case, and the comments make it visible.