Dynamic programming: state, transition and reconstruction
Connection and goal
Use the greedy lesson's coin counterexample and runtime-analysis foundations. Dynamic programming computes reusable subproblem answers. A solution needs a precise state meaning, exhaustive transition, base cases, dependency-respecting order and final answer. Repeated subproblems motivate reuse; optimal substructure justifies composing optimal answers.
1. Define the state before writing a formula
Unlimited positive integer denominations C, target nonnegative integer A: minimize the number of coins totaling exactly A. Let D[x] be the minimum count for exact amount x. Set D[0]=0; other amounts initially ∞. For x=1,...,A:
D[x]=min over c in C with c<=x of (1+D[x−c]), ignoring unreachable predecessors.
If no candidate exists, D[x]=∞. Positive denominations ensure x−c<x, so increasing x is a valid order. The answer is D[A], not the minimum over all table entries. Amount zero needs zero coins; initializing every state to zero would invent solutions to unreachable amounts.
2. Prove the transition
Any nonempty optimal solution for amount x has a final coin c. Removing it leaves a solution for x−c. If that remainder were not minimum, replacing it with a better one would improve the original, a contradiction. Thus an optimal solution appears among the transition's candidates. Conversely, each reachable candidate is a valid exact-x solution after adding c. Taking the minimum is both attainable and no larger than any optimum, so it is optimal. Induction on x proves the table.
3. Work a full small table
C={1,3,4}, A=6. Values D[0..6]=[0,1,2,1,1,2,2]. At x=5 candidates from coins 1,3,4 are 1+D[4]=2, 1+D[2]=3, 1+D[1]=2; choose 2. At x=6 candidates are 1+D[5]=3, 1+D[3]=2, 1+D[2]=3; choose coin 3 and answer 2. Greedy's 4+1+1 is worse.
For C={3,4}, A=2, D[1]=D[2]=∞. Do not report zero coins or subtract into negative array indices. In actual integer code avoid infinity+1 overflow: use a reachability check and a sufficiently safe sentinel, such as A+1 when all positive denominations are at least 1 and A+1 is representable.
4. Recover an actual solution
Alongside D[x], save choice[x]=c whenever a candidate strictly improves D[x]. For reachable A, start x=A, output choice[x], then set x=x−choice[x], until x=0. For amount 6, choose 3 then 3. Ties may be resolved consistently in any way; the count remains optimal, while the coin list can differ. Reconstruct only after checking D[A] is finite. Positive coins make reconstruction terminate.
5. Time, memory and top-down comparison
There are A+1 states; trying k denominations per state gives O(Ak) time and O(A) table/choice storage. Reconstruction takes O(number of coins output). This is pseudo-polynomial in A: binary input needs only Θ(log A) bits for the target, so O(Ak) is not polynomial in the bit-length of all input in general.
Memoized top-down recursion uses the same state and transition and caches each solved amount, potentially avoiding unreachable states. It still needs base cases, and without memoization repeated subproblems may cause exponential work. Bottom-up avoids recursive-call depth. Neither method automatically fixes a wrong state definition. This unlimited-coin state does not solve 0/1 coin usage; tracking which items remain is necessary there, as in the next lesson.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. For exact minimum-coin DP, D[0] is:
A. ∞ B. −1 C. 0 D. 1
Answer: C
A: Zero is reachable.
B: Counts cannot be negative.
C: Empty selection makes amount zero.
D: No coin is needed.
P02. C={1,3,4}, target 6: optimal minimum count?
A. 1 B. 2 C. 3 D. 6
Answer: B
A: No denomination 6.
B: 3+3 uses two.
C: This is largest-first greedy.
D: Six ones are feasible but not minimum.
P03. Why is increasing amount a valid evaluation order?
A. All denominations are equal B. Every predecessor x−c is smaller for positive c C. All answers are zero D. Greedy already solved it
Answer: B
A: Denominations may differ.
B: Dependencies have already been evaluated.
C: Only the zero base state is zero.
D: DP can correct greedy failures.
P04. C={3,4}, target 2 gives:
A. 0 coins B. 1 coin C. 2 coins D. Unreachable
Answer: D
A: Zero coins make zero, not two.
B: Neither denomination is two.
C: Any two coins total at least six.
D: No positive combination reaches two.
P05. Which stored information directly supports reconstruction?
A. Only target A B. A chosen coin for each improved state C. Only runtime D. Only number of denominations
Answer: B
A: Target does not identify transitions.
B: Following choices leads to predecessor amounts.
C: Runtime gives no solution path.
D: Denomination count does not specify chosen coins.
P06. O(Ak) for binary-encoded target A is called:
A. Always constant B. Pseudo-polynomial C. Always exponential in A D. Independent of A
Answer: B
A: It depends on A and k.
B: A can be exponential in its bit-length.
C: It is linear in A when k is fixed.
D: A is an explicit factor.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Algorithms syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in