REFERENCE SHEET

Dynamic programming & greedy choice

Identify what information a subproblem needs, or prove why a local choice is safe.

Before this Asymptotics & recurrences, Recursion, invariants & termination

D[a] = 1 + min{D[a−c] : c is a coin value and c≤a}; D[0]=0

Definitions

Dynamic programming

Solve a collection of overlapping subproblems once each, reusing their answers in a dependency order. Memoization is top-down; tabulation is bottom-up.

Optimal substructure

An optimal solution can be assembled from optimal solutions of the correctly specified subproblems.

Greedy algorithm

Commit to a local choice without revisiting it. A correctness proof must show that some optimum is compatible with each choice.

Key theorems

Interval scheduling

For unweighted intervals, repeatedly choosing the compatible interval with earliest finish time maximizes the number chosen. An exchange argument replaces the first interval of an optimum without reducing its remaining options.

Unbounded coin-change recurrence

For positive integer denominations and nonnegative target A, the displayed recurrence gives the minimum number of coins, with unreachable states +∞. Evaluate amounts increasingly in O(Ak) time for k denominations.

Notable applications

Sequence comparison

Edit distance uses prefix-pair states to compare strings.

Resource allocation

Knapsack and scheduling problems expose how state design captures remaining choices and constraints.

Work it out

Try before revealing

01 / Find a counterexample

With coins {1,3,4}, does repeatedly taking the largest possible coin minimize coins for amount 6?

Hint

Compare starting with 4 to using 3 twice.

Solution

Greedy returns 4+1+1, using 3 coins. The optimum is 3+3, using 2, so greedy fails.

02 / Compute

For coins {1,3,4}, compute D[0] through D[6].