13.23 Correctness Proofs for Dynamic Programming

A dynamic programming solution is easy to mistrust. The code may be short. The recurrence may look plausible. The table may produce correct answers on sample inputs. Yet a small mistake in the state meaning, transition, or base case can produce a solution that fails only on obscure cases.

Correctness proofs are the antidote. They force the algorithm to account for every valid solution, exclude every invalid solution, and justify why the value stored in each state is the desired value.

A good dynamic programming proof does not need to be long. It needs to be precise. Most DP correctness proofs follow a small number of reusable patterns.

Problem

How do we prove that a dynamic programming recurrence computes the correct answer?

The Core Proof Strategy

A dynamic programming proof usually has three parts:

Define the state precisely.
Prove the recurrence is correct.
Prove the computation order evaluates every state after its dependencies.

The recurrence proof is usually done by induction over the state order.

For one-dimensional DP, the induction variable may be:

$$ i $$

For interval DP, it may be:

$$ r-l+1 $$

For tree DP, it may be subtree height.

For graph DP, it may be topological order.

The proof structure follows the dependency structure.

Start with the State Meaning

A proof begins with a statement such as:

Let dp[i] be the minimum number of coins needed to form amount i.

or:

Let dp[i][j] be the length of the longest common subsequence of the first i characters of A and the first j characters of B.

This sentence is not decoration. It is the contract the recurrence must satisfy.

If the state meaning is vague, the proof cannot be made rigorous.

Bad:

dp[i] stores the answer up to i.

Good:

dp[i] stores the maximum sum of a non-empty subarray ending exactly at index i.

The word “exactly” often matters.

Example: Coin Change

Problem:

Given coin denominations,
find the minimum number of coins needed
to form amount x.

State:

$$ dp[x] $$

Meaning:

minimum number of coins needed
to form amount x

Base case:

$$ dp[0]=0 $$

Recurrence:

$$ dp[x] = 1+ \min_{c \le x} dp[x-c] $$

where (c) ranges over all coin denominations.

Proof of Coin Change

We prove by induction on (x) that (dp[x]) equals the minimum number of coins needed to form amount (x).

Base case:

For (x=0), no coins are needed. Therefore:

$$ dp[0]=0 $$

is correct.

Inductive step:

Assume (dp[y]) is correct for every (y < x).

Consider any optimal solution for amount (x). Its last coin has some denomination (c), where (c \le x). Removing that last coin leaves amount (x-c). By the induction hypothesis, the best way to form (x-c) uses (dp[x-c]) coins. Therefore any solution ending with coin (c) uses:

$$ dp[x-c]+1 $$

coins.

The recurrence checks every possible final coin and chooses the minimum. Thus it considers every valid optimal solution and selects the best one. Therefore (dp[x]) is correct.

This is the standard “last decision” proof.

The Two Inequality Method

For optimization DP, a rigorous proof often shows two inequalities.

Suppose the goal is minimization.

To prove:

$$ dp[state] = OPT(state) $$

show:

Upper Bound

The recurrence constructs a valid solution, so:

$$ OPT(state) \le dp[state] $$

or depending on convention:

dp is at least as good as some valid solution

Lower Bound

Every optimal solution is represented by some transition, so:

$$ dp[state] \le OPT(state) $$

Together, these prove equality.

In plain terms:

the DP never invents an invalid solution
the DP never misses the optimal solution

This method is especially useful when recurrences become complex.

Counting Proofs

Counting DP requires a different emphasis.

The proof must show:

every valid object is counted

no valid object is counted more than once

For example, in grid path counting:

$$ dp[i][j] = dp[i-1][j] + dp[i][j-1] $$

Every path to ((i,j)) must arrive either from above or from the left.

These two categories are disjoint.

Therefore adding the counts is correct.

Counting proofs often depend on partitioning the solution set into disjoint cases.

Example: Grid Paths

State:

$$ dp[i][j] $$

Meaning:

number of paths from (0,0) to (i,j)
using only right and down moves

Base cases:

$$ dp[0][j]=1 $$

$$ dp[i][0]=1 $$

Proof:

Every path to an interior cell ((i,j)) has a final move. Since only right and down moves are allowed, the final move must come from exactly one of:

$$ (i-1,j) $$

or:

$$ (i,j-1) $$

These two sets of paths are disjoint because their previous cells differ. Therefore the number of paths is the sum of the number of paths to those two cells. This gives the recurrence.

The base cases are correct because there is exactly one path along the top row or left column.

Feasibility Proofs

Feasibility DP stores booleans.

Example:

$$ dp[x] $$

means:

whether amount x can be formed

The recurrence often uses logical OR:

$$ dp[x] = \bigvee_c dp[x-c] $$

The proof must show both directions:

if the DP says true, a valid construction exists
if a valid construction exists, the DP will say true

This is the boolean version of the two inequality method.

Interval DP Proofs

Interval DP proofs usually use induction on interval length.

State:

$$ dp[l][r] $$

Meaning:

optimal value for interval [l,r]

Base case:

length 1 interval

Inductive step:

Assume all smaller intervals are correct.

For interval ([l,r]), every valid solution has some structural choice:

split point

last removed element

root element

matched endpoints

The recurrence enumerates that choice and combines smaller intervals. By induction, those smaller interval values are correct.

This is the standard proof template for matrix chain multiplication, file merging, burst balloons, and optimal binary search trees.

Tree DP Proofs

Tree DP proofs use induction on subtree size or height.

State:

$$ dp[u] $$

Meaning:

answer for subtree rooted at u

Base case:

leaf node

Inductive step:

Assume every child subtree is solved correctly.

Because child subtrees are disjoint and have no cycles, the parent can combine child results according to the recurrence.

For include/exclude DP, the proof also shows that parent choice correctly restricts child choices.

Example:

If node (u) is selected in an independent set, no child may be selected. If node (u) is not selected, each child may independently choose its best selected or unselected state.

Graph DP Proofs

Graph DP on DAGs is usually proved by topological order.

State:

$$ dp[u] $$

Meaning:

answer for paths ending at u

Proof:

Process vertices in topological order. When vertex (u) is processed, every predecessor of (u) has already been processed. Therefore all ways to reach (u), or all best values leading into (u), have already been accounted for.

The recurrence then propagates the correct value along outgoing edges.

Acyclicity is essential. Without it, the topological-order proof fails.

Proving the Computation Order

After proving the recurrence, you must show the algorithm evaluates states in a valid order.

Examples:

One-Dimensional DP

If:

$$ dp[i] $$

depends only on smaller indices, iterate increasing (i).

Interval DP

If:

$$ dp[l][r] $$

depends on shorter intervals, iterate by increasing length.

Tree DP

If a node depends on children, use postorder DFS.

DAG DP

If a node depends on predecessors, use topological order.

This part of the proof connects the recurrence to the implementation.

Proving Space Optimization

A compressed implementation needs its own justification.

For example, row-compressed LCS stores only:

previous row

current row

The proof must show that no older row is needed by the recurrence.

For 0/1 knapsack, reverse iteration must be justified:

capacity decreases
so each item is used at most once

Space optimization changes storage behavior, so correctness must account for overwrites.

Common Proof Mistakes

Proving the Code Instead of the State

Correctness belongs to the recurrence and state definition first.

Code follows afterward.

Ignoring Base Cases

Base cases are not trivial details. They anchor the induction.

Missing Exhaustiveness

A recurrence must consider every possible final decision.

If one case is missing, the proof fails.

Double Counting in Counting DP

Adding counts is valid only when cases are disjoint.

Assuming Independence

Subproblems must be combinable without hidden interaction.

This is especially important in interval and tree DP.

A Reusable Proof Template

For most DP algorithms, the following template works:

Define dp[state] as ...

We prove by induction over ... that dp[state]
equals the desired value for every state.

Base case:
...

Inductive step:
Assume the claim holds for all states that this state depends on.
Consider an optimal solution / valid object / feasible construction.
Its final decision must be one of ...
The recurrence enumerates all such decisions.
For each decision, the remaining subproblem is smaller,
so by the induction hypothesis its dp value is correct.
Therefore the recurrence computes exactly the desired value.

The algorithm evaluates states in dependency order,
so all required values are available when used.

This template covers a large fraction of dynamic programming proofs.

Takeaway

Correctness proofs for dynamic programming rest on precise state definitions, exhaustive transitions, valid base cases, and dependency-respecting computation order. Optimization DP proofs usually show that the recurrence neither invents invalid solutions nor misses the optimal one. Counting DP proofs show that valid objects are counted once and only once. Interval, tree, and graph DP proofs use induction over the natural dependency structure. Once these proof patterns become familiar, dynamic programming stops feeling like guesswork and becomes a disciplined method for deriving algorithms that are not only efficient, but demonstrably correct.