Dynamic Programming
Dynamic programming solves smaller subproblems once, stores their answers, and reuses them instead of repeating the work. A state records the information needed to define one subproblem; a recurrence explains how its answer follows from other states. In the formulations here, these dependencies form a directed acyclic graph: following them must not lead back to the same unfinished state. Memoization computes and caches answers when recursive calls need them; tabulation computes them in a chosen order, with dependencies first. The main design task is deciding what each state must remember and why the recurrence covers every valid choice.
Design checklist
- State: What minimum information makes the remaining problem independent of the path used to reach it?
- Value: What does
dp[state]mean—feasibility, count, minimum cost, maximum value, or a witness? - Transition: Which smaller states can produce this state?
- Base cases: What are the smallest valid subproblems?
- Order: Does every dependency exist before it is read?
- Answer: Which state or aggregate contains the requested output?
Top-down versus bottom-up
State count multiplied by transition work gives the first complexity estimate. Memory can be compressed only when overwritten states will never be needed for future transitions or reconstruction.
Correctness pattern
Prove that the state captures all relevant history, then use induction over the dependency order: assuming smaller states are correct, the recurrence considers every valid final choice and selects or combines them according to the objective.
When DP is the wrong tool
DP is unhelpful when the chosen state still depends on unbounded history, the state space is larger than direct search, or a greedy/exchange property removes the need to compare alternatives. Expanding state can restore correctness, but may make the algorithm impractical.
Worked state design: minimum coins
With unlimited positive integer denominations [1,3,4], largest-coin-first makes 6 as 4+1+1 (three coins), while 3+3 uses two. A counterexample disproves this greedy rule; overlapping subproblems alone do not prove a replacement recurrence.
Define dp[t] as the minimum number of coins summing exactly to t. Set dp[0]=0; an impossible amount starts at infinity, not zero. For positive t, try each coin c no larger than t and minimize 1+dp[t-c]. Every solution has a final coin, and removing it leaves exactly that smaller amount, so these choices are exhaustive. Positive denominations ensure strictly smaller dependencies. For amounts 0 through 6 the values are [0,1,2,1,1,2,2]. Time is O(Tk), space O(T), for target T and k denominations. For [4] and target 6 the answer is unreachable.
def min_coins(coins, target):
if target < 0 or any(c <= 0 for c in coins):
raise ValueError("positive denominations and nonnegative target required")
dp = [0] + [float("inf")] * target
for amount in range(1, target + 1):
for coin in coins:
if coin <= amount:
dp[amount] = min(dp[amount], 1 + dp[amount - coin])
return dp[target]
assert min_coins([1, 3, 4], 6) == 2
assert min_coins([4], 6) == float("inf")
assert min_coins([], 0) == 0
The same method in different states
Fibonacci starts with one index and reusable earlier values. 0/1 knapsack adds item availability and capacity; longest common subsequence uses two prefix lengths. Shortest-path DP explains which graph order makes distance dependencies acyclic. These examples differ in what the state must remember, not in whether they use a table.
In the USF coin-change workbench, choose coins [1, 4, 6, 10] and amount 8, then compare Change Greedy with Change Table. The greedy choice needs three coins, while the table finds 4 + 4. Use the memoized mode to see where stored answers replace repeated calls.