Dynamic Programming & Capstone

A schedule repeats the same question

A repair workshop has several jobs. Each job has a start time, a later finish time and a value, and one bench can handle only one job at a time. Which jobs should the workshop accept to earn the most?

For this lesson, consider four jobs in finish-time order: A runs from 0 to 2 with value 3; B from 1 to 4 with value 6; C from 2 to 5 with value 5; D from 4 to 7 with value 5. Jobs may touch at an endpoint, so D can follow B. The best total is 11, using B and D.

The obvious method tries every subset of jobs, throws away the subsets that overlap, and keeps the most valuable one left. Four jobs have $2^4=16$ subsets, of which 8 fit on the bench. With $n$ jobs there are $2^n$ subsets, so this method examines up to $2^n$ candidate schedules. Thirty jobs already mean more than a billion.

from itertools import combinations

jobs = [(0, 2, 3), (1, 4, 6), (2, 5, 5), (4, 7, 5)]

def fits(chosen):
    pairs = combinations(chosen, 2)
    return all(a[1] <= b[0] or b[1] <= a[0] for a, b in pairs)

def best_by_subsets(jobs):
    sizes = range(len(jobs) + 1)
    subsets = [c for k in sizes for c in combinations(jobs, k)]
    feasible = [c for c in subsets if fits(c)]
    best = max(sum(job[2] for job in c) for c in feasible)
    return len(subsets), len(feasible), best

assert best_by_subsets(jobs) == (16, 8, 11)

The waste is easy to point at. Whether or not the workshop accepts D, it must still decide what to do with A and B, and that smaller decision has the same answer both times. This module is about asking each such question once. You need vectors, references, search and cost reasoning from the earlier modules. The lab practises the same skills on other problems, with instances of its own.

Why the greedy instinct fails

A greedy rule commits to a locally attractive choice and never reconsiders it. Two rules suggest themselves here. Taking the job that finishes earliest, again and again, always gives the largest number of jobs on one bench. But the workshop wants the largest total value, and on the four jobs that rule takes A and C for only 8. The other rule takes the most valuable remaining job that still fits.

On the four jobs, most-valuable-first takes B, then D, and reaches 11. That is luck, not a guarantee. Let one job occupy time 0 to 6 with value 8, and let two jobs occupy 0 to 3 and 3 to 6 with value 5 each. Most-valuable-first takes the long job and earns 8; the two short jobs together earn 10. No tie is involved, so no tie-breaking rule rescues it.

def largest_first(jobs):
    chosen = []
    for job in sorted(jobs, key=lambda job: -job[2]):
        if fits(chosen + [job]):
            chosen.append(job)
    return sum(job[2] for job in chosen)

trap = [(0, 3, 5), (3, 6, 5), (0, 6, 8)]
assert largest_first(trap) == 8
assert best_by_subsets(trap)[2] == 10
assert largest_first(jobs) == 11

This is one computed counterexample to one specific rule. It does not show that every greedy rule fails on every problem. It shows that a rule needs a proof for the objective at hand, and this one has none.

Give each cell a sentence

Sort the jobs by finish time and number them 1 to $n$. Let best[i] mean: the largest total value achievable using only the first i jobs. The empty prefix has best[0] = 0.

One more number per job makes the idea work. For job $j$, let $p(j)$ be the number of jobs that finish no later than job $j$ starts. Touching counts as compatible: a job that finishes at 4 is counted for a job that starts at 4. Because the jobs are sorted by finish time, the jobs counted by $p(j)$ are exactly the first $p(j)$ jobs. For the workshop, $p$ is 0, 0, 1, 2: nothing fits before A or B, only A fits before C, and A and B both finish in time for D.

Now consider job $i$. Either the best schedule for the first $i$ jobs leaves it out, or it includes it. If it leaves it out, the answer is best[i - 1]. If it includes it, every other chosen job must finish by the time job $i$ starts, so the rest of the schedule lives inside the first $p(i)$ jobs.

$$\text{best}[i]=max(\text{best}[i-1],v_i+\text{best}[p(i)])$$

The recurrence is not a formula to memorize. It follows from the sentence that defines the cell. A state like this is sufficient when two properties hold. First, the future depends on the past only through the state: any two histories that reach best[i] face the same remaining choices. Second, every state a cell reads comes earlier in a fixed order, so it can be finished first. Both hold here. Nothing about which earlier jobs were chosen changes what job $i$ may do, and both $i-1$ and $p(i)$ are below $i$, because every job takes some time.

Without the sort, the compatible jobs would be scattered, and no single prefix would describe them. The representation is part of the correctness argument.

Remember each answer

Write the recurrence as a function that calls itself: to answer prefix 4, ask for prefix 3 and for prefix $p(4)=2$. Prefix 3 asks for prefix 2 and prefix 1. So prefix 2 is requested twice, once by 4 and once by 3, and each request repeats everything beneath it. On four jobs the plain recursion makes 15 requests. On a chain of $n$ jobs where $p(i)=i-2$, the count obeys $c(n)=1+c(n-1)+c(n-2)$, which grows like ${1.618}^n$: exponential, though below the $2^n$ upper bound.

Memoization keeps each answer the first time it is worked out and returns it on every later request. Each prefix is then computed once, and the same four jobs take 9 requests: one to start, and two from each of the four prefixes that do any work.

p = [sum(1 for j in range(i) if jobs[j][1] <= jobs[i][0])
     for i in range(4)]
assert p == [0, 0, 1, 2]

def plain(i, requests):
    requests.append(i)
    if i == 0:
        return 0
    skip = plain(i - 1, requests)
    take = jobs[i - 1][2] + plain(p[i - 1], requests)
    return max(skip, take)

def remembered(i, requests, memo, share=True):
    requests.append(i)
    if i == 0:
        return 0
    if i in memo:
        return memo[i]
    if not share:
        memo = dict(memo)
    skip = remembered(i - 1, requests, memo, share)
    take = jobs[i - 1][2] + remembered(p[i - 1], requests, memo, share)
    memo[i] = max(skip, take)
    return memo[i]

asked = []
assert plain(4, asked) == 11
assert len(asked) == 15 and asked.count(2) == 2
asked = []
assert remembered(4, asked, {}) == 11 and len(asked) == 9
asked = []
assert remembered(4, asked, {}, share=False) == 11
assert len(asked) == 15

A memo also needs a way to say "not worked out yet" that cannot be confused with a real answer. Zero is a legitimate best value here, so zero cannot be the marker.

Trace the completed prefixes

The recursion discovers which prefixes it needs. But the recurrence already says which ones: every cell reads only cells to its left. So the cells can simply be filled from left to right, with no recursion at all. That is tabulation.

def best_table(jobs):
    jobs = sorted(jobs, key=lambda job: job[1])
    best = [0]
    tests = 0
    for i, (start, finish, value) in enumerate(jobs):
        compatible = 0
        for j in range(i):
            tests += 1
            if jobs[j][1] <= start:
                compatible = j + 1
        best.append(max(best[-1], value + best[compatible]))
    return best, tests

assert best_table(jobs) == ([0, 3, 6, 8, 11], 6)
assert best_table(trap)[0][-1] == 10

This model finds each boundary with a plain scan so that the state is easy to inspect. The table, the 6 compatibility tests and every number quoted about the two schedules are checked by these blocks.

The table invariant and proof

Prove this by induction. The empty prefix is correct because selecting nothing has value zero. Assume the earlier entries are correct. Every schedule for the first $i$ jobs either omits job $i$ or includes it. A schedule that omits it is a schedule for the first $i-1$ jobs, so its value is at most best[i - 1]. A schedule that includes it has all its other jobs among the first $p(i)$, so its value is at most $v_i$ plus best[p(i)]. No schedule beats the larger of the two.

Both candidates are also achievable: reuse an optimal schedule for the first $i-1$ jobs, or append job $i$ to an optimal schedule for the first $p(i)$ jobs, which cannot overlap it. So the maximum is neither too large nor too small, and the invariant holds for $i$. The proof relies on additive values, one bench, and the endpoint convention. Setup costs between jobs, or a second bench, would need a different state.

That last sentence is the discipline to keep. If one history consumes a special permit and another does not, a prefix index alone cannot tell them apart, and a table that merges unlike futures is efficiently wrong.

Memoization and tabulation are schedules of work

Both methods compute the same states from the same recurrence. They differ in who decides the order: the recursion, on demand, or a loop, in advance. Here are both in C++ on the workshop's jobs.

#include <algorithm>
#include <vector>

struct Job {
    int start;
    int finish;
    long long value;
};

// p[i]: how many jobs finish no later than job i starts.
// The jobs are already sorted by finish time.
std::vector<int> boundaries(const std::vector<Job>& jobs) {
    const int n = static_cast<int>(jobs.size());
    std::vector<int> p(n, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (jobs[j].finish <= jobs[i].start) p[i] = j + 1;
        }
    }
    return p;
}

// Best total using only the first i jobs, remembered once known.
// known and memo are references: every call shares them.
long long best_first(int i, const std::vector<Job>& jobs,
                     const std::vector<int>& p,
                     std::vector<bool>& known,
                     std::vector<long long>& memo) {
    if (i == 0) return 0;
    if (known[i]) return memo[i];
    const long long skip = best_first(i - 1, jobs, p, known, memo);
    const long long take =
        jobs[i - 1].value + best_first(p[i - 1], jobs, p, known, memo);
    memo[i] = std::max(skip, take);
    known[i] = true;
    return memo[i];
}

// The same states, filled left to right.
long long best_table(const std::vector<Job>& jobs,
                     const std::vector<int>& p) {
    const int n = static_cast<int>(jobs.size());
    std::vector<long long> best(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        const long long take = jobs[i - 1].value + best[p[i - 1]];
        best[i] = std::max(best[i - 1], take);
    }
    return best[n];
}

int main() {
    const std::vector<Job> jobs = {
        {0, 2, 3}, {1, 4, 6}, {2, 5, 5}, {4, 7, 5}};
    const std::vector<int> p = boundaries(jobs);
    std::vector<bool> known(jobs.size() + 1, false);
    std::vector<long long> memo(jobs.size() + 1, 0);
    const long long remembered = best_first(4, jobs, p, known, memo);
    const long long tabled = best_table(jobs, p);
    return remembered == 11 && tabled == 11 ? 0 : 1;
}

This program keeps a separate known vector, so any value at all may be a real answer. A single vector with a marker value is shorter, and correct whenever the marker can never be an answer.

Bottom-up filling uses no call stack, so a long chain of states cannot exhaust it, and the completed frontier is easy to see. Memoization computes only the states a query actually reaches, which matters when most of a large table is never needed. Neither is better in general: consider how sparse the needed states are, how deep the recursion goes, and how many queries follow. A recurrence whose dependencies form a cycle has no valid order at all, and neither method repairs that.

Count transitions, not answers

Count the work in a stated model: one step per comparison or addition of numbers that fit in a machine word. The table has $n+1$ cells and each is filled with a constant number of steps once its boundary is known. The simple scan above makes exactly $n(n-1)/2$ compatibility tests on every input, after a sort that takes $O(n\log n)$ comparisons, so the whole method takes $\Theta (n^2)$ steps.

Because the finish times are sorted, each boundary can instead be found by binary search, the half-open search of Module 11. That is $O(\log n)$ comparisons per job, and $O(n\log n)$ comparisons in total for sorting, searching and filling, in the worst case, with $O(n)$ memory.

The number of schedules can be exponential while the number of states is linear. That is the benefit of representing the question well. It does not make every table cheap: a state with several independent dimensions has a product of sizes, and that product is the cost.

Some tables are indexed by a number in the input instead of by a position. Take the question "can some of these $n$ weights add up to exactly $T$?" A table with one true-or-false cell per total from 0 to $T$ answers it in $O(nT)$ steps. That looks polynomial, but $T$ is written with only about ${\log }_{2}T$ bits, and adding one bit to $T$ doubles the table. A bound like this is called pseudo-polynomial: polynomial in the value of $T$, exponential in the length of its encoding. Calling it "polynomial" hides a difference that matters when the numbers are large.

Large answers need a numerical contract

Totals and counts can outgrow their type even when the table is small. Signed integer overflow is undefined behavior in C++, not a wrap-around you may rely on. A wider return type does not repair additions already performed in a narrower type: the table entries, the accumulator and the return type must all match the promised range.

#include <limits>
#include <vector>

long long total_values(const std::vector<int>& values) {
    const long long most = std::numeric_limits<long long>::max();
    long long total = 0;
    for (int value : values) {
        if (value < 0) return -1;
        if (value > most - total) return -1;
        total += value;
    }
    return total;
}

int main() {
    const std::vector<int> values = {
        1000000000, 1000000000, 1000000000};
    return total_values(values) == 3000000000LL ? 0 : 1;
}

Three values of one billion sum to three billion, which no 32-bit int holds, so the accumulator is long long from its first addition. The function assumes nonnegative inputs and returns -1 for a violation or an overflow. Whatever failure marker an interface chooses, its meaning must be documented.

A marker is a label, not a number. Code that feeds a marker into arithmetic, or compares it as if it were a value, computes nonsense quietly. Test for the marker first, then compute. Similarly, reject a negative size before it is converted to an unsigned vector size.

An optimum value is not yet an explanation

The table says the best total is 11. It does not say which jobs earn it. To recover them, walk back from the last cell. At cell $i$, if best[i] equals best[i - 1], job $i$ was not needed: move to $i-1$. Otherwise job $i$ is in the schedule: record it and jump to $p(i)$. For the workshop the walk records D, jumps to prefix 2, records B, jumps to prefix 0 and stops. The jobs arrive last to first, so reverse them if the caller expects chronological order.

best, _ = best_table(jobs)
walk, i = [], 4
while i > 0:
    if best[i] == best[i - 1]:
        i -= 1
    else:
        walk.append("ABCD"[i - 1])
        i = p[i - 1]
assert walk == ["D", "B"]

The walk needs the whole best table, or else one remembered choice per cell made while filling. Either costs $O(n)$ memory here. The walk itself takes at most $n$ moves, because every move goes to a smaller index. That is also its termination argument.

Ties need a policy. If several schedules have equal value, returning any of them is often enough. If the interface promises a particular one, such as the earliest, the rule must be stated, built into the comparisons and tested. A test that accepts only one optimal schedule without stating the rule rejects correct programs.

Validate the reconstruction separately from the value: the returned jobs must come from the input, must not overlap, and must sum to the computed optimum. A correct table with a wrong walk is still a wrong schedule function.

Memory follows the dependencies

If a recurrence reads only a bounded number of earlier cells, a rolling buffer of that many cells can replace the table. But dropping old cells drops the information the walk back needs. Decide which output is required before optimizing storage: "only the best total" and "the chosen jobs" are different products.

A two-dimensional table stored as nested vectors has independent row objects. Filling rows in the wrong order reads cells that are not yet established. When a row is overwritten in place, the direction of the loop decides which values are still old, and that needs its own argument.

The browser drawings are bounded teaching output. A check on a large instance may skip the drawing while still computing the answer. Keep computation and observation separable, so that a cost claim describes the algorithm and not the recording.

A problem that looks different

An audio editor must choose nonoverlapping clips to keep as much approved speech as possible. Each clip has a known score. Why might taking the longest remaining clip first fail? Describe the state an optimal selection needs, and decide whether an endpoint search, a stored choice, or both would be useful.

Practise

The lab has five exercises. You make a slow recursive count remember its answers and compare the number of calls; fill a grid table one cell at a time; build two tables for an increasing subsequence and walk back along them; and then meet a new problem whose design is yours. That last exercise asks for your reasoning before your code, and it counts your program's work. Every picture comes from your own program's execution, including the empty and impossible cases.

Finish an explorer you can defend

The capstone is a project of your own. It is optional and ungraded, and its time is not part of this module's estimate.

Build an Algorithm Explorer in the course's preview: choose at least three algorithms from Modules 10–12. Each one draws its state and calls frame() at every step, and each has checks written with CHECK, including one empty or impossible case. Add a short explanation of each design.

For each algorithm, write down its input contract, its invariant, the operation you count and one edge case. The explanation should connect representation to behavior: what every stored value means, which references stay valid, and what makes each loop terminate. A handsome viewer with undefined behavior or unchecked preconditions is unfinished.

Recap

You can now: define a sufficient state, derive and prove its recurrence, compute it by memoization or by a table, and walk back to the choices under a stated tie policy.

Invariant: every completed cell answers exactly the subproblem its label states, and a cell reads only cells that are already complete.

Complexity achieved: weighted job selection in $O(n\log n)$ worst-case comparisons and $O(n)$ memory, against up to $2^n$ subsets; a table indexed by an input number is pseudo-polynomial.

Failure mode: a state that merges different futures, a memo copied instead of shared, a marker fed into arithmetic, or a correct value with a wrong walk back.

In real software: this lesson makes no claim about a named system. The constraints it names are checkable in your own program: integer ranges, storage, and whether the caller needs the choices or only the value.

Retrieval: Module 11's binary search kept a half-open range. How does that convention find $p(j)$ without ever forming an index of $-1$?

Check yourself

1. Which two properties make a proposed state sufficient, and how does each hold for best[i]?
2. Why does the proof need both an upper bound over all schedules and a schedule that achieves the candidate value?
3. With a rolling buffer in place of the full table, what can the function still return, and what can it no longer return?

Original SciMigo course material. C++ examples target C++17.