Dynamic programming and Bellman recurrences

Return to weighted interval scheduling, with positive-duration half-open intervals and nonnegative rewards. Sort jobs by finish time and label them one through n. Let p(j) be the greatest earlier index whose job finishes no later than job j starts, or zero if no such index exists. Define V(j) as the largest total reward obtainable using only the first j jobs. This prefix is sufficient because the ordering makes every job compatible with a chosen last job belong to an earlier compatible prefix.

An optimal prefix solution either excludes job j or includes it. Exclusion leaves the first j minus one jobs. Inclusion earns its reward and allows only jobs among the first p(j). Replacing a suboptimal compatible prefix with a better one would improve the full solution, so the included prefix must itself be optimal. The recurrence compares both cases rather than claiming one is always safe. Nonnegative rewards simplify interpretation, although allowing an empty schedule also handles negative rewards by skipping them.

All dependencies point to smaller indices, so a bottom-up loop computes V(0), V(1), and onward through V(n). Alternatively, memoized recursion evaluates a value on demand and saves it for later calls. Both methods implement the same recurrence; the dependency structure explains why neither needs to solve a subproblem before its own prerequisites are available. Counting n entries is not enough for a time bound: count the work to determine each p(j) and evaluate each transition too.

After sorting, binary searching the finish times computes each p(j) in logarithmic time, for O(n log n) comparison work overall. Once those indices exist, the recurrence takes O(n) additions and comparisons of rewards. Store a choice or compare the recorded values during backtracking to reconstruct actual jobs. Reporting only V(n) loses the witness schedule. Ties allow several optima; a consistent tie rule produces one witness without implying uniqueness. Exact arithmetic costs depend on the bit lengths of accumulated rewards.

The principle of optimality says an optimal complete decision sequence contains an optimal continuation for the state it reaches. The state must include every quantity that affects feasibility or future costs. If a budget is omitted, two apparently identical prefixes may have different affordable continuations. If previous choices change a setup cost, recording only the current time may be insufficient. Adding the missing information can repair correctness while greatly increasing the number of states. That increase is a real computational cost, not a bookkeeping inconvenience.

Not every Bellman-looking equation has an immediate one-pass solution. Cyclic state dependencies may require a finite-horizon expansion, repeated relaxation, or a separate fixed-point argument with suitable assumptions. Likewise, an integer-capacity table with W columns takes time polynomial in W, not necessarily in the binary length of W. This is the pseudopolynomial distinction from recurrence analysis. A good dynamic-programming solution therefore presents the state meaning, recurrence proof, base cases, evaluation order, complexity model, and witness recovery as one connected argument.