Recognizing DP

A recursion has **overlapping subproblems** when the same call is made many times with the same arguments. The Fibonacci recursion fib(n) = fib(n - 1) + fib(n - 2) is the classic: fib(5) calls fib(4) and fib(3), and fib(4) calls fib(3) again. Run the animation on n = 5 and 6 and watch fib(3) and its whole subtree reappear in the recursion tree.

The waste grows fast. The plain recursion makes 15 calls for n = 5, 25 for n = 6, 67 for n = 8 and 177 for n = 10, about 1.6 times more with every increment of n, while only n + 1 distinct values exist. A problem is a candidate for dynamic programming when the number of distinct subproblems is small (polynomial) but the plain recursion explores exponentially many calls.

1static long calls;
2
3static long fib(int n) {
4    calls++;
5    if (n <= 1) return n;
6    return fib(n - 1) + fib(n - 2);              // fib(n - 2) is recomputed inside fib(n - 1)
7}
8
9static long callsFor(int n) {
10    calls = 0;
11    fib(n);
12    return calls;                                // 15 for n = 5, 25 for 6, 67 for 8, 177 for 10
13}

1static long fib(int n) {
2    if (n <= 1) return n;                       // base cases
3    return fib(n - 1) + fib(n - 2);             // two recursive calls
4}

**Optimal substructure** means the best answer to the whole problem is built from best answers to smaller subproblems. For fewest coins to make an amount, the last coin c in an optimal solution leaves amount - c, and the rest must itself be an optimal solution for amount - c, because otherwise swapping in a better one would improve the whole.

That argument gives the recurrence best(a) = 1 + min over coins c <= a of best(a - c), with best(0) = 0. Substructure is half of the recipe; overlapping subproblems is the other half. If subproblems did not repeat, the plain recursion would be fine; if substructure failed (the best answer to the whole needs a non-best answer to a part), the recurrence would give wrong answers.

Not every optimisation has the property. The longest simple path in a graph does not: the longest path from A to C through B does not consist of the longest path from A to B followed by anything, because those two parts might share vertices.

1// fewest coins for amount, plain recursion; returns -1 when impossible
2static int minCoins(int[] coins, int amount) {
3    if (amount == 0) return 0;
4    int best = Integer.MAX_VALUE;
5    for (int c : coins) {
6        if (c > amount) continue;
7        int sub = minCoins(coins, amount - c);   // optimal answer for the smaller amount
8        if (sub != -1) best = Math.min(best, sub + 1);
9    }
10    return best == Integer.MAX_VALUE ? -1 : best;
11}

1static int minCoins(int[] coins, int amount) {
2    int INF = amount + 1;
3    int[] dp = new int[amount + 1]; Arrays.fill(dp, INF); dp[0] = 0;             // dp[a] = fewest coins that make a
4    for (int a = 1; a <= amount; a++)
5        for (int c : coins)
6            if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;          // one coin c, then solve a - c
7    return dp[amount] >= INF ? -1 : dp[amount];
8}
9static long ways(int[] coins, int amount) {
10    long[] dp = new long[amount + 1]; dp[0] = 1;                                 // one way to make 0: take nothing
11    for (int c : coins)                                                          // coins in the outer loop: each combination is counted once
12        for (int a = c; a <= amount; a++) dp[a] += dp[a - c];
13    return dp[amount];
14}

Think of every subproblem as a **node** and every dependency (the transition 'to solve this, I need that') as a **directed edge**. Because each subproblem depends on smaller ones, the graph has no cycles: it is a **directed acyclic graph** (DAG), and a valid evaluation order is any topological order of it.

Many problems become path problems on this graph. Climbing stairs with steps of 1 or 2 has nodes 0..n and edges i to i + 1 and i + 2; the number of ways is the **number of paths** from 0 to n, which for n = 7 is 21. Minimum-cost climbing and coin change ask for the **shortest path** from the start to the goal, with costs on edges or nodes; maximum-loot problems ask for the **longest path**, which is easy on a DAG.

This view tells you the running time too: dynamic programming visits each node once and each edge once, so the cost is the number of states plus the number of transitions.

1// number of paths from node 0 to node n in the DAG with edges i -> i+1 and i -> i+2
2static long countPaths(int n) {
3    long[] paths = new long[n + 1];
4    paths[0] = 1;
5    for (int node = 0; node < n; node++) {       // nodes in topological order: increasing index
6        paths[node + 1] += paths[node];          // edge node -> node + 1
7        if (node + 2 <= n) paths[node + 2] += paths[node];   // edge node -> node + 2
8    }
9    return paths[n];
10}

1static long ways(int n) {                         // dp[i] = number of ways to reach step i with moves of 1 or 2
2    long[] dp = new long[n + 1]; dp[0] = 1;       // one way to stand at the start: do nothing
3    if (n >= 1) dp[1] = 1;
4    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];   // arrive from i-1 or from i-2
5    return dp[n];
6}
7static long waysRolling(int n) {
8    long prev2 = 1, prev1 = 1;                    // dp[0], dp[1]
9    for (int i = 2; i <= n; i++) { long cur = prev1 + prev2; prev2 = prev1; prev1 = cur; }   // forget what is no longer needed
10    return prev1;
11}

The **state** is the set of values that identifies a subproblem. A good state has two properties. It is **sufficient**: it contains everything the future decisions depend on, and nothing about the past beyond that. And it is **small**: few enough distinct values for the table to fit. For the 0/1 knapsack, the state is (number of items considered, capacity left): the best value for the remaining items depends only on those two numbers, not on which items were taken already.

Common choices: a prefix length i for one sequence, a pair (i, j) of prefix lengths for two sequences, an amount or capacity, a subset as a bit mask, and an extra flag when a rule depends on the previous choice. The next lessons define the state before anything else: when a DP goes wrong, the state is the first suspect.

1static int knapsack2D(int[] w, int[] v, int cap) {
2    int n = w.length; int[][] dp = new int[n + 1][cap + 1];            // dp[i][c]: best value from the first i items with capacity c
3    for (int i = 1; i <= n; i++)
4        for (int c = 0; c <= cap; c++) {
5            dp[i][c] = dp[i - 1][c];                                    // skip item i
6            if (c >= w[i - 1]) dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - w[i - 1]] + v[i - 1]);   // or take it
7        }
8    return dp[n][cap];
9}
10static int knapsack1D(int[] w, int[] v, int cap, boolean backwards) {
11    int[] dp = new int[cap + 1];
12    for (int i = 0; i < w.length; i++) {
13        if (backwards) for (int c = cap; c >= w[i]; c--) dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);   // right to left: dp[c - w] still excludes item i
14        else           for (int c = w[i]; c <= cap; c++) dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);   // left to right: item i may be taken again (a bug for 0/1)
15    }
16    return dp[cap];
17}

The **transition function** (or recurrence) says how to compute a state from smaller ones. In the house-robber problem, best(i) is the most loot from the first i houses. The i-th house is either skipped, leaving best(i - 1), or robbed, which forces skipping its neighbour and gives best(i - 2) + value(i). So best(i) = max(best(i - 1), best(i - 2) + value(i)).

Write the transition as an enumeration of the **last decision**: every optimal solution made some final choice, and each choice leads to a smaller state plus a known gain or cost. List all the choices, take the best, and the recurrence follows. In the “Classic” preset (2, 7, 9, 3, 1) the table ends at 12, and the animation shows each cell as the larger of its two options.

1static int rob(int[] value) {
2    int n = value.length;
3    int[] best = new int[n + 1];                 // best[i]: most loot from the first i houses
4    for (int i = 1; i <= n; i++) {
5        int skip = best[i - 1];
6        int take = (i >= 2 ? best[i - 2] : 0) + value[i - 1];
7        best[i] = Math.max(skip, take);          // the last decision is skip or take
8    }
9    return best[n];
10}

1static int rob(int[] a) {                             // no two adjacent houses
2    int n = a.length; int[] dp = new int[n + 1];      // dp[i] = best loot from the first i houses
3    dp[1] = a[0];
4    for (int i = 2; i <= n; i++)
5        dp[i] = Math.max(dp[i - 1], dp[i - 2] + a[i - 1]);   // skip house i, or rob it and use the best before the neighbour
6    return dp[n];
7}