23.08Intermediate4 topics14 min1 interactive animation

DP correctness

Why a dynamic programming solution is correct: state completeness, acyclic dependencies and induction on the state order, with a stress-testing harness.

Learning goals

Check that a state is complete, with every future-relevant fact included
Verify that the dependency graph is acyclic and name an evaluation order
Prove a recurrence correct by induction over the states in evaluation order
Cross-check a DP against brute force on small random inputs

Prerequisites

The DP workflowReconstructing solutions

A table that fills without errors can still be wrong. Three short checks, each corresponding to part of the proof, catch nearly every incorrect dynamic programming solution.

23.08.1

State completeness

A state is **complete** when the best way to finish from it depends on nothing but the state. If the rules refer to something the state forgets, the recurrence quietly optimises the wrong problem. Take 'pick numbers with the largest sum so that no three consecutive numbers are picked'. The state 'best for the first i numbers' is incomplete, because whether number i + 1 may be picked depends on how many of the last numbers were picked. Adding the **current streak** (0, 1 or 2) completes it.

The test: write down what the future decisions need and make sure the state implies it. If two histories lead to the same state but allow different futures, the state is too small. If a state contains facts the future never uses, it is too large and wastes time and memory.

Java

1// largest sum with no three consecutive picks; dp[i][k] = best for the first i numbers, ending with k consecutive picks (k = 0, 1, 2)
2static int maxSumNoThree(int[] a) {
3    int NEG = Integer.MIN_VALUE / 2;
4    int[][] dp = new int[a.length + 1][3];
5    for (int[] row : dp) Arrays.fill(row, NEG);
6    dp[0][0] = 0;
7    for (int i = 1; i <= a.length; i++) {
8        dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1], dp[i - 1][2]));   // skip number i: streak resets
9        dp[i][1] = dp[i - 1][0] + a[i - 1];                                        // pick it, starting a streak
10        dp[i][2] = dp[i - 1][1] + a[i - 1];                                        // pick it, extending a streak
11    }
12    return Math.max(dp[a.length][0], Math.max(dp[a.length][1], dp[a.length][2]));
13}

23.08.2

Dependency acyclicity

The recurrence must not be circular. A state that depends, directly or through others, on itself has no value to compute. Check that **every dependency points to a state that is evaluated earlier**: smaller index, smaller amount, fewer items, a strict subset. When that holds, the loop order in the bottom-up code is a topological order and a top-down recursion terminates.

A recurrence like f(i) = min(f(i - 1), f(i + 1)) + cost[i] has cycles (i depends on i + 1, which depends on i), and plain dynamic programming does not apply. Shortest paths in graphs with cycles need Dijkstra or Bellman-Ford, because the states have no natural order. Look at the DAG view: if the graph has a cycle, use a graph algorithm.

Java

1// deps.get(s) lists the states that s depends on; returns true when the dependency graph has no cycle (Kahn's algorithm)
2static boolean isAcyclic(int states, List<List<Integer>> deps) {
3    int[] pending = new int[states];
4    List<List<Integer>> users = new ArrayList<>();
5    for (int s = 0; s < states; s++) users.add(new ArrayList<>());
6    for (int s = 0; s < states; s++) for (int d : deps.get(s)) { pending[s]++; users.get(d).add(s); }
7    Deque<Integer> ready = new ArrayDeque<>();
8    for (int s = 0; s < states; s++) if (pending[s] == 0) ready.add(s);
9    int done = 0;
10    while (!ready.isEmpty()) {
11        int s = ready.poll();
12        done++;
13        for (int u : users.get(s)) if (--pending[u] == 0) ready.add(u);
14    }
15    return done == states;                       // every state could be evaluated after its dependencies
16}

23.08.3

Induction on state order

The correctness proof of a DP is an **induction over the evaluation order**. Claim: for every state s, the computed value equals the true optimum for s. *Base:* the base cases are correct by definition. *Step:* assume every state before s is correct (the inductive hypothesis); the recurrence for s combines those values over all possible last decisions, and by optimal substructure the best of the combinations is the optimum for s.

For house robber: base best[0] = 0 is correct (no houses, no loot). Step: the optimum for the first i houses either skips house i, whose best is the optimum for the first i - 1 houses, or robs it, which forbids house i - 1 and leaves the optimum for the first i - 2 houses plus value i. These two cases are exhaustive, so the larger is the optimum.

Backing the proof with a cheap **stress test** catches implementation slips the proof does not: run the DP and a brute force on thousands of random small inputs and compare.

Java

1// stress test: the DP must agree with exhaustive search on every small random input
2static boolean stressHouseRobber(int trials, long seed) {
3    Random rnd = new Random(seed);
4    for (int t = 0; t < trials; t++) {
5        int n = rnd.nextInt(10);
6        int[] value = new int[n];
7        for (int i = 0; i < n; i++) value[i] = rnd.nextInt(20);
8        if (robDp(value) != robBrute(value)) return false;   // a counterexample: print 'value' to debug
9    }
10    return true;
11}
12
13static int robDp(int[] value) {
14    int skip = 0, take = 0;
15    for (int v : value) { int nt = skip + v; skip = Math.max(skip, take); take = nt; }
16    return Math.max(skip, take);
17}
18
19static int robBrute(int[] value) {
20    int best = 0;
21    for (int mask = 0; mask < (1 << value.length); mask++) {
22        if ((mask & (mask >> 1)) != 0) continue;             // two adjacent houses chosen
23        int sum = 0;
24        for (int i = 0; i < value.length; i++) if ((mask >> i & 1) == 1) sum += value[i];
25        best = Math.max(best, sum);
26    }
27    return best;
28}

House robber: take it or skip it

Interactive · edit the input

house money

2h1

7h2

9h3

3h4

1h5

dp[i] = best from the first i houses

0none

2rob h1

?i=2

?i=3

?i=4

?i=5

Setup

For the first i houses, the best loot either skips house i (best of the first i−1) or robs it (its money plus the best of the first i−2, because the neighbour is off limits).

Step 1 / 6

Java

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}

Live state

houses

No condition evaluated on this step

Execution trace (dry run table)Show 6 steps

Step	Line	State	What happens
1	L3	houses=5	For the first i houses, the best loot either skips house i (best of the first i−1) or robs it (its money plus the best of the first i−2, because the neighbour is off limits).
2	L5	i=2 skip=2 rob=7 dp[i]=7	House 2: skipping keeps 2; robbing gives dp[0] + 7 = 7. Best 7 (rob it).
3	L5	i=3 skip=7 rob=11 dp[i]=11	House 3: skipping keeps 7; robbing gives dp[1] + 9 = 11. Best 11 (rob it).
4	L5	i=4 skip=11 rob=10 dp[i]=11	House 4: skipping keeps 11; robbing gives dp[2] + 3 = 10. Best 11 (skip it).
5	L5	i=5 skip=11 rob=12 dp[i]=12	House 5: skipping keeps 11; robbing gives dp[3] + 1 = 12. Best 12 (rob it).
6	L6	return=12 houses=[1, 3, 5]	Maximum loot 12. Tracing the take/skip decisions backwards from house 5 gives the houses [1, 3, 5].

23.08.4

Transition exhaustiveness

The recurrence must list **every legal last decision** and **only legal ones**. Missing an option makes the answer too poor (the optimum may be one you never considered); including an illegal option makes it infeasible. Exhaustiveness is the other half of the induction step above: the 'best of the combinations' is the optimum only if the combinations cover every possibility.

Edit distance (the fewest insertions, deletions and replacements turning one string into another) is the standard illustration. At the last characters you either match them for free, replace one, delete one or insert one, four cases in all. Dropping 'replace' still gives a plausible-looking table but computes something else: for "kitten" and "sitting" the correct answer is 3, while a table with only insertions and deletions gives 5.

A practical check is to write the decision as a sentence, 'the last thing that happens is one of: ...', and count the cases against the code's branches.

Java

1// dp[i][j] = fewest edits turning the first i characters of a into the first j characters of b
2static int editDistance(String a, String b) {
3    int m = a.length(), n = b.length();
4    int[][] dp = new int[m + 1][n + 1];
5    for (int i = 0; i <= m; i++) dp[i][0] = i;                  // delete everything
6    for (int j = 0; j <= n; j++) dp[0][j] = j;                  // insert everything
7    for (int i = 1; i <= m; i++) {
8        for (int j = 1; j <= n; j++) {
9            int same = a.charAt(i - 1) == b.charAt(j - 1) ? 0 : 1;
10            dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1,      // delete a's last character
11                                         dp[i][j - 1] + 1),     // insert b's last character
12                                dp[i - 1][j - 1] + same);       // match (0) or replace (1)
13        }
14    }
15    return dp[m][n];
16}
17
18// the same table with the replace option left out: insertions and deletions only
19static int editDistanceNoReplace(String a, String b) {
20    int m = a.length(), n = b.length();
21    int[][] dp = new int[m + 1][n + 1];
22    for (int i = 0; i <= m; i++) dp[i][0] = i;
23    for (int j = 0; j <= n; j++) dp[0][j] = j;
24    for (int i = 1; i <= m; i++) {
25        for (int j = 1; j <= n; j++) {
26            dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1) ? dp[i - 1][j - 1] : Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
27        }
28    }
29    return dp[m][n];
30}

Practice ladder

Now try it yourself

Easy

House Robber (stress test)
Min Cost Climbing Stairs (stress test)

Medium

Paint House
Best Time to Buy and Sell Stock with Cooldown

Advanced

Best Time to Buy and Sell Stock IV
Dungeon Game

Key takeaways

A state is complete when the best finish depends only on the state; add the missing fact otherwise.
Every dependency must point to an earlier state; a cycle means a graph algorithm, not plain DP.
Correctness is induction over the evaluation order: base cases, then the recurrence over all last decisions.
Stress-test the DP against brute force on small random inputs.