How would you prove a cheapest multi-leg travel itinerary has optimal substructure?
answer
- the claim is about optimal parts
- assume optimal, then cut it
- swap in a cheaper piece
- derive a contradiction with the whole
- name additivity and independence
basics
~20 sA cheapest itinerary's prefix must itself be cheapest: swapping in a cheaper A-to-M portion would make the whole cheaper, contradicting optimality. The argument needs fares to add across the cut and the two portions to be independent.
solid answer
~50 sThe proof is the cut-and-paste (exchange) argument. Take a cheapest itinerary from A to Z and cut it at some intermediate hub M. Suppose the A-to-M portion is not a cheapest A-to-M itinerary. Then paste the cheaper one in place of it: total fare is the sum of the two portions' fares, so the whole itinerary just got cheaper — contradicting that we started with a cheapest one. Therefore the A-to-M portion is optimal, and the same holds for M-to-Z. Two conditions make the argument work and both must be stated: the objective is **additive** across the cut, and the two subproblems are **independent** — choosing the A-to-M portion imposes no constraint on what M-to-Z may use. That independence clause is where the property fails for other problems, so an interviewer will listen for it.
go deeper
Be ready to state the property in plain words: the best overall answer is made of best answers to its parts. Recognise that this is an assumption you must justify, not something every problem has.
Explain the cut-and-paste argument end to end — assume optimality, cut at a boundary, substitute a better piece, derive the contradiction — and name additivity and independence as the conditions it relies on.
Demonstrate that you run this proof before writing a recurrence, and that when the exchange step fails you first ask whether your subproblem definition is missing state rather than discarding the approach.
Own the cost side of the answer: restoring independence by widening the state is always available, so the real decision is whether the resulting state space is affordable at production input sizes or whether an approximation is the better trade.
## What the property claims A problem has **optimal substructure** when an optimal solution to the whole problem *contains within it* optimal solutions to its subproblems. It is a claim about structure, not about speed. Overlapping subproblems is what makes dynamic programming fast; optimal substructure is what makes the recurrence *correct*. If you write a recurrence for a problem that lacks it, you get an algorithm that runs quickly and returns wrong answers. ## The standard proof technique Optimal substructure is proved by **cut-and-paste**, also called an exchange argument, and it is always the same three moves: 1. **Assume** you hold an optimal solution to the whole problem. 2. **Cut** it at a chosen boundary, exposing a piece that solves a subproblem. 3. **Suppose** that piece is not optimal for its subproblem, paste a better one in its place, and show the whole solution improved — contradicting step 1. Concretely, for a cheapest itinerary from origin A to destination Z under per-leg fares: let the optimal itinerary pass through hub M, splitting into an A-to-M portion costing `x` and an M-to-Z portion costing `y`, total `x + y`. If some A-to-M itinerary costs `x' < x`, then concatenating it with the existing M-to-Z portion yields an A-to-Z itinerary costing `x' + y < x + y`. That contradicts the assumed optimality of the original. Hence `x` was already the cheapest A-to-M fare. Symmetrically for `y`. The recurrence falls straight out of the argument: the cheapest fare from A to Z is the minimum, over candidate intermediate hubs M, of (cheapest A-to-M) plus (cheapest M-to-Z). You did not invent the recurrence and then hope; you derived it from a proof. ## The two conditions the argument silently uses A candidate who recites the contradiction without naming these has memorised a ritual. **Additivity (a decomposable objective).** The total cost must be a function of the pieces' costs — here a plain sum. If the fare structure were, say, a discount that applies only when the *whole* itinerary stays on one carrier, then improving a portion in isolation could raise the total, and the paste step would be invalid. **Independence.** The two subproblems must not compete for the same resources or constrain each other. Substituting a different A-to-M portion must leave the M-to-Z portion still legal and still costing `y`. If the pieces shared a budget, a seat inventory, or — the classic case — a requirement not to revisit any city, then the paste can produce something that is cheaper on paper but not a valid solution at all. Independence is the clause that distinguishes problems where this proof works from problems where it collapses. ## Why interviewers push on this Saying "this problem has optimal substructure" is the load-bearing claim in any DP answer, and it is the one candidates assert rather than argue. The follow-up — *prove it* — is a routine probe. What a strong answer sounds like: > "Cut an optimal A-to-Z itinerary at any hub it passes through. If the prefix were not a cheapest route to that hub, I could substitute a cheaper prefix and keep the same suffix, producing a cheaper total — contradiction. The substitution is legal because fares add across the cut and because the suffix does not depend on which route reached the hub." That is four sentences and it contains the assumption, the cut, the exchange, the contradiction, and both side conditions. ## Things that are not the property - **"It breaks into smaller pieces of the same kind"** is decomposition, which nearly every recursive problem has. Optimal substructure additionally requires that the *optimal* whole contains *optimal* parts. - **"I can write a recurrence"** is not evidence. Anyone can write a recurrence; the question is whether it is sound. - **A greedy choice being safe** is a different and stronger claim: that one specific locally-best step is guaranteed to appear in some optimal solution. Optimal substructure is compatible with having to try every candidate boundary. - **Minimising versus maximising** is irrelevant. Maximisation problems can have perfectly good optimal substructure; what matters is additivity and independence, not the direction of the objective. ## How to use it in practice Before filling any table, state the subproblem in one sentence ("cheapest fare from A to this hub"), then run cut-and-paste in your head against it. If you cannot complete the exchange step — usually because substituting one piece would break the other — that is a signal that your subproblem definition is missing state, or that the problem genuinely lacks the property and DP will not save you.
- What in that proof would break if a discount applied only to itineraries staying on one carrier?The additivity assumption. Total fare would no longer be the sum of the two portions' fares, so pasting a cheaper A-to-M portion could lose the whole-itinerary discount and raise the total. The exchange step becomes invalid, and the plain sum-of-parts recurrence is unsound unless the carrier is folded into the subproblem state.
- Does optimal substructure tell you which intermediate hub to cut at?No. It only guarantees that whichever boundary the optimal solution crosses, the pieces on either side are themselves optimal. Since you do not know the boundary in advance, the recurrence takes a minimum over all candidate hubs. Knowing the boundary without searching would be a greedy-choice claim, which is a strictly stronger and separately provable property.
- How can a wrong subproblem definition make optimal substructure appear to fail?If the subproblem omits state that the rest of the solution depends on, the pieces stop being independent and the exchange breaks. Adding the missing dimension to the subproblem — a carrier, a remaining budget, a parity — often restores independence at the cost of a larger state space. Failure of the exchange is a signal to re-examine the state before abandoning the approach.
saying these in an interview costs you the question
- Treats 'breaks into smaller pieces' as the whole property
- Asserts optimal substructure without any exchange argument
- Never mentions that subproblems must be independent
- Assumes the objective is additive without saying so
- Confuses optimal substructure with a safe greedy choice
- Thinks maximisation problems cannot have optimal substructure