Motivation
A greedy algorithm commits to a choice without reconsidering it. Dynamic programming retains the alternatives that may matter and solves a family of related subproblems. Both can be efficient, but neither is justified by a slogan. Greedy methods require a proof that the chosen commitment can appear in an optimum. Dynamic programming requires a proof that the state records enough information to describe every relevant continuation.
The aim is to make these obligations visible. We begin with interval scheduling, where a local choice is provably safe, then change the objective to show why the proof breaks. Weighted scheduling and knapsack illustrate how a recurrence can repair that loss of information. All input collections below are finite, and an empty feasible selection is allowed.
Definitions
Definition 2.3.1
(Feasibility, optimality, and an exchange argument)
An optimization problem specifies a set of feasible solutions and an objective to maximize or minimize. A greedy choice selects one next component according to a local rule. An exchange argument proves that an optimal solution can be modified to contain the greedy choice while remaining feasible and not worsening the objective. The argument must also justify how the remaining problem is represented after the choice.
Definition 2.3.2
(Dynamic-programming states)
A state specifies a subproblem and its value. A recurrence expresses that value using smaller states, together with base cases. Optimal substructure means an optimum can be assembled from optimal solutions of the subproblems identified by the recurrence. Overlapping subproblems means different recursive branches require the same state. Memoization computes a needed state once on demand; tabulation computes states in a dependency-respecting order.
Optimal substructure is not a license to discard context arbitrarily. For a path problem with a restriction against repeating vertices, the current endpoint alone may not describe the legal continuations; previously used vertices can matter. A state must retain whatever affects future feasibility or cost. Conversely, remembering the complete history can create exponentially many states. State design balances sufficiency against the number of distinct states.
Theorems
Theorem 2.3.3
(Earliest finishing time solves unweighted interval scheduling)
Given intervals with , the algorithm that repeatedly selects a compatible remaining interval with earliest finishing time returns a maximum-cardinality collection of pairwise nonoverlapping intervals. Endpoints may touch: an interval ending at time is compatible with one starting at . Sorting by finish time and scanning takes time.
Theorem 2.3.4
(Weighted interval scheduling recurrence)
Sort intervals by nondecreasing finish time and assign nonnegative weights . Let be the largest index less than whose interval ends no later than , or zero if none exists. If is the maximum weight from the first intervals, then
With predecessor indices computed by binary search, tabulation and sorting take time and auxiliary storage, under constant-time exact weight arithmetic.
Proof sketch or proof idea
Proof
(Earliest finish: exchange and residual problem)
For the greedy theorem, let finish earliest among all remaining intervals, and let be the first interval in some optimal schedule, listed in time order. Replace by . Since , every later interval of that schedule starts no earlier than and therefore no earlier than . The replacement remains feasible and has the same cardinality. Hence an optimum containing exists.
After choosing , the only eligible intervals start at or after . If the remainder of an optimum containing were not optimal for this residual problem, a better residual solution could be appended to , contradicting optimality. Induct on the number of eligible intervals. The empty case is immediate, and the exchange plus residual argument proves each step. Sorting once implements the rule: scan in finish order and accept an interval exactly when it starts no earlier than the finish of the last accepted one. Equal finish times can be broken arbitrarily; the proof uses only a non-strict comparison.
Proof X-ray
What the exchange preserves
Replacing an optimal schedule's first interval by an earlier-finishing one preserves compatibility with everything after it. It also preserves the number selected. These are the two facts supporting the greedy proof. A weighted objective loses the second fact: the replacement may be much lighter. Dynamic programming repairs this precise failure by comparing the include and exclude cases instead of committing to one exchange.
Proof
(Weighted recurrence: exclude or include the last interval)
For the weighted recurrence, partition all feasible solutions from the first intervals according to whether they contain interval . An excluding solution has weight at most , and that value is attainable. If a solution includes , every earlier chosen interval must finish at or before , since its finish time is no later than and positive-length intervals cannot fit after while still finishing no later than it. The eligible earlier intervals are precisely the prefix through . Their best weight is , and appending attains . Taking the better of these exhaustive alternatives proves the recurrence.
All referenced indices are smaller than , so increasing-index tabulation is valid. A naive recursive expansion can revisit the same index many times; storing each value prevents that duplication. At most states are evaluated, each doing constant work after its predecessor is known. Sorting and binary searches supply the stated overall time. If weights are long integers, their bit-operation costs must be included rather than silently treated as constant.
Recovering a solution, not just its value
The table stores optimal values, but a user may need the actual selected intervals. Starting at , compare with . If the first is chosen, skip and move to . If the second is chosen, output and move to . A consistent tie rule can choose either branch. Each move decreases the index, so reconstruction terminates after at most steps. The recurrence proof ensures each chosen branch can be completed optimally; reversing the output list gives time order.
A value table without reconstruction is not necessarily wrong, but it solves only the value version of the problem. The specification should distinguish these outputs. Similarly, storing one arbitrary greedy partial schedule at every state would lose the comparison between alternatives that makes the dynamic program correct.
Concept lensStructural
Weighted scheduling as a longest path
Take vertices and two kinds of edges: of length zero, and of length . A path from to uses the second kind of edge into exactly for the intervals it selects, and it can reach again only after intervals ending no later than . So its length is the weight of a compatible set, every compatible set arises, and is the longest-path length to . The reconstruction walk is that path read backwards.
Zero-one knapsack and a numeric state parameter
Proposition 2.3.5
(Zero-one knapsack recurrence)
Suppose item has positive integer size and nonnegative value , and capacity is a nonnegative integer. Each item can be taken at most once. Let be the best value using items one through with total size at most . The bases are and, because sizes are positive, . If , then . Otherwise,
Proof
(Zero-one knapsack: exclude or include the last item)
The proof again splits feasible solutions into those excluding and including the last item. In the latter case removing that item leaves a feasible solution at capacity using only earlier items. An inferior remainder could be replaced by an optimum, so the displayed value is attainable and bounds every solution. The reference to row is essential: it prevents taking item repeatedly.
The table has states, giving arithmetic operations and storage, conventionally written for . Value-only storage can be reduced to by updating capacities in descending order for each item. At the moment capacity is updated, every smaller capacity still holds the previous row's value, so the inclusion branch cannot reuse the current item. Ascending updates instead solve a different reuse-allowing recurrence. Reconstructing all selected items needs retained decisions or a separately justified reconstruction method; one compressed row alone does not automatically provide those decisions.
Because binary has only logarithmically many bits, is pseudopolynomial, not a general polynomial bound in encoded input length. If is exponential in that length, the table is exponential too. Dynamic programming is a design method, not a guarantee of polynomial time.
A different question: fill the capacity exactly
The preceding state allows unused space. If the specification requires total size exactly , the empty selection is not a feasible answer at every capacity. Define to be the maximum value of a subset of the first items whose sizes sum to , and write when no such subset exists. Thus but for every . With the same positive integer sizes, the exhaustive include-or-exclude argument now gives
Proof
(Exact-fill recurrence)
The exclusion and inclusion branches cover all subsets, and removing item from an exact- subset leaves exact size in the previous row. Conversely, any reachable predecessor gives an attainable candidate; adding a finite value to still means impossible. Induction on proves both the values and the impossible entries. The at-most value is recovered by , because the possible exact sizes partition the at-most solutions.
In code, test reachability before adding: do not add to a finite sentinel that might overflow or accidentally beat a real value.
Worked example 2.3.6
(Unused capacity versus an impossible exact fill)
With items and , exact size is impossible: the possible subset sizes are . The at-most-capacity- optimum is nevertheless , using the first item and leaving two units unused. At exact size both items give . This distinction also matters when the optimum is zero: with one item , exact size is reachable with value , whereas exact size is impossible. Initializing both to zero loses that distinction.
A one-row implementation can use the same descending capacity order as above, provided unreachable entries start at and the predecessor is checked before addition. It returns a value or impossibility, not automatically a chosen subset. Keeping the item-by-capacity decisions (including reachability and a consistent tie rule) supports reconstruction; treating a numerical sentinel as a real choice can invent a subset. The number of states and the pseudopolynomial dependence on numeric are unchanged.
Reading a dependency graph
Each state can be viewed as a vertex, with an edge to every state on which it depends. A legal table order places dependencies first. In weighted scheduling, all edges go to smaller indices; in knapsack, all edges go to the previous row. This acyclic structure supplies an induction proving that every computed entry equals its intended value. A recurrence that refers back to itself without a smaller state requires additional reasoning and cannot simply be evaluated in a loop.
For every new dynamic program, write a sentence giving the exact meaning of one state, specify its legal parameter range, and derive alternatives from feasible solutions. Then verify the base cases, evaluation order, number of states, work per state, and reconstruction. These checks identify distinct errors: a correct recurrence can be implemented in the wrong order, and a correct table can be analyzed with an incorrect state count. They also reveal whether preprocessing, such as computing predecessors, dominates the total cost.
Worked examples
Counterexample mode
Earliest finish fails once weights are added
Claim: the earliest-finishing rule also maximizes total weight. Take of weight one and of weight one hundred. Earliest finishing time selects , which ends first, and blocks because the two overlap; the total is one. Selecting alone gives one hundred. The unweighted exchange replaces an interval by an earlier-finishing one: it preserves compatibility and the number of intervals, but not the weight. The repair is the weighted recurrence, which compares inclusion and exclusion. This counterexample identifies the failed proof step; it does not imply that all greedy algorithms fail on every weighted problem.
Worked example 2.3.7
(A weighted table with a genuine choice)
Let the finish-sorted intervals be of weight three, of weight six, and of weight four. Their predecessor indices are . The table is , , , and . Reconstruction selects intervals three and one, whose touching endpoints are compatible. Merely choosing the individually heaviest interval would return six instead of seven.
Worked example 2.3.8
(The direction of a compressed knapsack update)
With one item of size two and value three and capacity four, the zero-one optimum is three. Starting from a zero row, an ascending update first sets capacity two to three and then uses that new entry at capacity four, obtaining six and using the same item twice. Descending order processes capacity four before capacity two, reading the old zero entry at capacity two and correctly keeping the value three.
Counterexample mode
Value-per-size greedy fails for zero-one knapsack
A tempting rule takes items in decreasing value-to-size ratio while they fit. With capacity and items , the ratios are . The rule takes , after which neither remaining item fits in the four free units, so its value is . The two size-five items together fit and are worth . The rule is optimal only when items may be split; the recurrence handles the all-or-nothing choice.
Common mistakes
Common mistake
(An exchange that ignores the objective)
An exchange argument must preserve feasibility and the objective, and justify the residual problem; demonstrating that the chosen interval is short or early is not enough. A counterexample should satisfy every input assumption, including positive interval length and endpoint conventions.
Common mistake
(Treating a numeric-capacity table as polynomial)
A table indexed by a numeric capacity can hide exponential dependence on the input bits. With the knapsack table has states, while the binary encoding of has only bits. The bound is pseudopolynomial.
Common mistake
(Compressing rows without tracking which row is read)
A memory optimization must preserve which logical row each referenced entry represents. For one item of size two and value three and capacity four, an ascending in-place update gives , using the item twice, instead of the correct .
A recurrence needs both an upper-bound argument covering every feasible solution and a construction attaining each candidate value. Counting only states omits transition work: the cost is the number of states times the work per state.
Summary
Greedy scheduling works because an exchange places the earliest-finishing choice in an optimum without reducing the number selected. Weights destroy that exchange, so a recurrence retains inclusion and exclusion alternatives. Weighted scheduling and zero-one knapsack demonstrate state meanings, dependencies, reconstruction, and the distinction between polynomial and pseudopolynomial time.
Exercises
Quick check
(Give a counterexample to choosing the shortest interval first in unweighted interval scheduling, with strict positive lengths.)
Solution · Answer
Use , , and . The last is the unique shortest, and choosing it blocks both other intervals, giving one instead of two. Touching the first two endpoints is allowed under the half-open convention.
Exercise 2.3.9
(For intervals with respective weights , compute predecessor indices, the value table, and an optimal schedule.)
Core
Solution(3)
- 1
Compute the predecessor indices
Because: The intervals are already in finish order , and is the largest earlier index whose interval ends no later than .
- 2
Fill the value table
Key step
- 3
Backtrack to an optimal schedule
At state four, inclusion gives , so select interval four and move to . At state two, inclusion gives , so select interval two and move to . State one selects interval one. These three compatible intervals have weight , exceeding the single weight-seven interval.
Quick check
(Explain why the zero-one knapsack recurrence is still correct if some values are negative, while the empty selection remains allowed.)
Solution · Answer
Inclusion/exclusion still partitions all feasible solutions, and every branch remains attainable, so the recurrence computes the true maximum whatever the signs of the values. The empty selection gives value zero, so the maximum never needs to select a negative-value item. Positivity of the sizes is used only for the base and so that is a strictly smaller capacity, which a descending in-place update has not yet overwritten.
Exercise 2.3.10
(The denominations are one, three, and four. Show that repeatedly taking the largest available coin is not optimal for making six, and derive a minimum-coin recurrence for a general nonnegative target.)
Synthesis
Solution(4)
- 1
Refute the largest-coin rule at target six
Greedy takes four, one, one, using three coins; three plus three uses two.
- 2
Define the state
Let be the fewest coins making total , with . Since a coin of value one exists, every target is feasible.
- 3
Split by the last coin
Key step
Replacing the remainder by an optimum for cannot increase the count, and appending the coin to such an optimum attains the candidate. Hence for ,
Because: Every solution has a last coin of some allowed denomination , leaving target .
- 4
Evaluate in increasing order of the target
Each entry uses smaller entries only, so all values through the desired target take a linear number of arithmetic operations in that numeric target, a pseudopolynomial bound for binary-encoded targets.