Skip to main content

Optimal Substructure: When a Problem Admits DP

What This Concept Is​

Dynamic programming evaluates a family of related subproblems and reuses their answers. For optimization, the central question is state sufficiency: can histories represented by the same state use the same future decisions and costs? An optimal-substructure argument establishes that replacing a subsolution by a better one preserves feasibility and improves or preserves the whole objective.

This is a claim about the chosen state and objective, not a property inferred from a problem's name. Counting and feasibility DPs need sound decompositions too, even though they have no optimum. Overlap explains why reuse saves work; it is not a necessary condition for every computation called DP. Tree DP can combine each subtree once. Nor does a valid recurrence imply polynomial time.

For the finite, acyclic DPs in this module, provide: the state meaning, legal transitions, boundary values, decreasing dependency measure, answer location, and a proof that no feasible solution is lost or illegal solution introduced.

Why It Matters Here​

A cache makes a wrong recurrence faster. An omitted constraint can leave all sample outputs correct while merging histories whose future choices differ. State design therefore comes before table layout and optimization. When an attempt fails, test the state using two concrete histories, rather than adding coordinates without explaining their role.

Concrete Examples​

Rod cutting. For integer length l, prices p[k], unlimited pieces of each allowed positive length, and no cutting fee, let R(l) be the best revenue from using the entire rod. R(0)=0 and R(l)=max(p[k]+R(l-k)) over allowed k<=l. An impossible remainder has value negative infinity, not zero. Every cutting has a first piece; replacing its remainder preserves total length. Conversely, each candidate composes a legal cutting. Induction on l proves the recurrence. With lengths 1..4 and prices [1,5,8,9], values are [0,1,5,8,10]; length 4 uses two length-2 pieces. A fee per physical cut changes the combination rule.

Longest simple path. Endpoint alone is insufficient on a general graph. With edges s->a, a->u, s->b, b->u, u->a, a->t, paths s,a,u and s,b,u share endpoint u but only the second may extend through a. State (visited subset, endpoint) repairs the missing information, at exponential cost. This problem admits a subset DP; it does not inherit the small endpoint-only DP of a DAG. In a DAG, extending through a later vertex cannot revisit a prefix vertex.

Counting paths. In a right/down obstacle grid, count paths by their last move. The two classes are disjoint, so add their counts. There is no optimal-substructure claim to make: the proof is completeness and no double counting.

Common Confusion / Misconceptions​

  • A scalar "best so far" is enough only when worse histories cannot enable a better continuation. For two resource constraints, one scalar budget can lose feasible alternatives; define both resources or prove a dominance rule.
  • Optimal substructure does not promise efficiency: Held-Karp still has an exponential subset coordinate.
  • A failed endpoint-only state is not a proof that no DP exists.
  • A memoized function must depend on its key and fixed input. Reading mutable prices without cache invalidation violates that contract.

How To Use It​

Write the sentence "D(state) is the [count/best value/feasibility] of ... subject to ...". List exactly what future choices observe. Try to construct two histories with the same key but different legal continuations. Then prove both directions: decompose every solution into a candidate, and compose each candidate into a solution. Finish with induction over a stated measure. Count states and candidate transitions separately before deciding whether the recurrence fits the input.

Check Yourself​

Why does (remaining capacity) alone fail for 0/1 knapsack but work for an unbounded variant with fixed available types? Which proof changes when the output is a count rather than a maximum? Can an exponential DP be correct?

Mini Drill or Application​

Prices are [2,5,7,8] for lengths 1..4. Derive the exact-use rod recurrence and solve length 4. Then charge 2 per cut. Feedback: without fees, two length-2 pieces give 10. With fees they give 8, tying the uncut rod; do not charge for the final piece. The state may stay length-only if the fee rule is fixed.

Read This Only If Stuck​

Use Skiena's book index to locate limitations of DP and longest simple paths; use CLRS for rod cutting and elements of DP. Stop after writing your own replacement argument. Topic names are assignments, not edition-specific section claims.