Dynamic Programming

The greedy procedure left behind an expensive remainder because it never questioned the largest coin it took. The cure was clear and was already used in the previous lesson: solve the remainder too, that is, compute and store the optimal solution of every subproblem. That procedure’s name is dynamic programming.

The approach’s appeal is that it brings an exponential search down to a countable table. Its cost is two separate preconditions, and either can break silently. The first is optimal substructure: the optimal solution can be built from the optimal solutions of subproblems. The second is overlapping subproblems: the same subproblem is asked more than once. When the first breaks, the answer comes out wrong; when the second breaks, the answer stays correct but storing gains nothing. This lesson counts both.

• DA29. The measured problem: the largest sum obtainable by selecting at most three non-adjacent elements in an array. An empty selection is allowed, so the answer is never below zero.
• DA30. The oracle sees every subset: a 12-element array has 4096 subsets.
• DA31. A step is a recursive call in memoization, computing a cell in the bottom-up table, or trying a subset in the oracle.
• DA32. Memoization adds a memo table to the recursive solution; the bottom-up solution builds the same recurrence without recursion.
• DA33. The approach’s precondition: the memo’s key must carry the entire state that uniquely determines the subproblem. An incomplete key breaks only this precondition.
• DA34. The second precondition is optimal substructure, and it is kept unbroken in this lesson; the case where it breaks belongs to the classical problems topic.
• DA35. The overlap measurement is taken directly from the shared definition and is not redefined.
• DA36. Memo size is measured by entry count, table size by cell count.
• DA37. Every measurement is also run on a second corpus with seed 20260219.

Overlap Is Counted

Memoization’s gain equals how many times subproblems repeat. This is not something to be guessed but something to be counted. The two procedures below run for the same $n$; in one, every subproblem is asked twice, in the other, every call produces a new subproblem.

# Overlap measurement from the shared definition: same n, two different subproblem structures.
class Counter:
    def __init__(self):
        self.steps = 0

    def add(self, n=1):
        self.steps += n


def overlapping(n, memoized=True):
    """Overlapping subproblems: every value is called twice."""
    s = Counter()
    memo = {}

    def f(k):
        s.add()
        if k < 2:
            return k
        if memoized and k in memo:
            return memo[k]
        d = f(k - 1) + f(k - 2)
        memo[k] = d
        return d
    f(n)
    return {"calls": s.steps, "entries": len(memo)}


def non_overlapping(n, memoized=True):
    """Non-overlapping subproblems: every call is a different subproblem."""
    s = Counter()
    memo = {}

    def f(start, end):
        s.add()
        if end - start <= 1:
            return end - start
        if memoized and (start, end) in memo:
            return memo[(start, end)]
        mid = (start + end) // 2
        d = f(start, mid) + f(mid, end)
        memo[(start, end)] = d
        return d
    f(0, n)
    return {"calls": s.steps, "entries": len(memo)}


print(" n  overlap memoized  overlap unmemoized  no-overlap memoized  no-overlap unmemoized  memo")
for n in (10, 15, 20):
    a, b = overlapping(n, True), overlapping(n, False)
    c, d = non_overlapping(n, True), non_overlapping(n, False)
    print(f"{n:2d} {a['calls']:16d} {b['calls']:19d} {c['calls']:21d}"
          f" {d['calls']:22d} {c['entries']:6d}")

 n  overlap memoized  overlap unmemoized  no-overlap memoized  no-overlap unmemoized  memo
10               19                 177                    19                     19      9
15               29                1973                    29                     29     14
20               39               21891                    39                     39     19

In the overlapping structure, for $n = 20$, the call count drops from 21,891 to 39; a 561-times gain. In the non-overlapping structure, for the same $n$, the memoized and unmemoized versions both make 39 calls — the memo never hits even once — yet it still holds 19 entries. What the second row says is clear: memoization’s condition is overlap. Without overlap, the memo table only takes up space; the answer stays correct, the gain is zero, and memory goes to waste.

The difference between the two structures lies in the shape of the recurrence. In the overlapping structure, two branches descend to the same values, and the subproblem space is of size $n$; in the non-overlapping one, every branch descends into its own range, and the subproblem space is as large as the call count. This is the question to ask before choosing an approach: is the subproblem space smaller than the call count.

The Memo’s Key Must Carry the Entire State

Memoization’s second and quieter precondition concerns the memo table. The problem below has a two-variable state: which position we are at, and how many choices we have left. The same procedure is run with two different keys.

# Continuing from the previous block: Counter comes from there.
SEED = 20260218
PICKS = 3          # maximum number of elements that can be selected


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def corpus(seed=SEED, n=40, length=12):
    r = generator(seed)
    return [{"no": i + 1, "array": [r(30) - 9 for _ in range(length)]}
            for i in range(n)]


def oracle_select(array, k, s):
    """Sees every subset; values those that are non-adjacent and at most k elements."""
    best = 0
    for mask in range(1 << len(array)):
        s.add()
        if mask & (mask << 1):                    # two adjacent picks exist
            continue
        if bin(mask).count("1") > k:
            continue
        best = max(best, sum(array[i] for i in range(len(array))
                              if mask >> i & 1))
    return best


def memoized(array, k, s, key="full"):
    """key='full' -> memo keyed by (position, remaining); 'partial' -> position only."""
    memo = {}

    def f(i, remaining):
        s.add()
        if i >= len(array) or remaining == 0:
            return 0
        memo_key = (i, remaining) if key == "full" else i
        if memo_key in memo:
            return memo[memo_key]
        d = max(f(i + 1, remaining), array[i] + f(i + 2, remaining - 1))
        memo[memo_key] = d
        return d
    result = f(0, k)
    return result, len(memo)


def measure(key, items):
    diverging, approach_total, oracle_total, entries = [], 0, 0, 0
    for item in items:
        s1, s2 = Counter(), Counter()
        value, size = memoized(item["array"], PICKS, s1, key)
        if value != oracle_select(item["array"], PICKS, s2):
            diverging.append(item["no"])
        approach_total += s1.steps
        oracle_total += s2.steps
        entries += size
    return {"diverging": len(diverging), "diverging_no": diverging[:6], "approach_steps": approach_total,
            "oracle_steps": oracle_total, "ratio": round(oracle_total / approach_total, 2), "memo_entries": entries}


items = corpus()
print("oracle: per array,", 2 ** 12, "subsets")
for key in ("full", "partial"):
    print(f"memo key {key:8s}:", measure(key, items))

oracle: per array, 4096 subsets
memo key full    : {'diverging': 0, 'diverging_no': [], 'approach_steps': 2440, 'oracle_steps': 163840, 'ratio': 67.15, 'memo_entries': 1200}
memo key partial : {'diverging': 39, 'diverging_no': [1, 2, 3, 5, 6, 7], 'approach_steps': 1000, 'oracle_steps': 163840, 'ratio': 163.84, 'memo_entries': 480}

Three numbers side by side. The oracle spends 163,840 steps on 40 inputs. Full-key memoization spends 2440 steps — 67.15 times fewer than the oracle — and diverges on none of the 40 inputs. Partial-key memoization spends 1000 steps, 163.84 times fewer than the oracle, and diverges from the oracle on 39 of the 40 inputs.

The mechanism of this error differs from the previous two lessons’ and is more dangerous. Nothing is skipped here; the procedure visits every branch. The problem is that the value written to the memo belongs to the wrong question. The best value computed at the fifth position with three picks remaining is returned when that same position is reached with only one pick remaining. The memo hits, the computation is skipped, the step count drops — and the answer breaks. The drop in step count here is not a speedup but a symptom of the error: 1000 steps instead of 2440, the memo holding 480 entries instead of 1200, means that more than half of the subproblems that should be computed are never computed at all.

Memoization Versus Bottom-Up

The same recurrence can also be built without recursion. This is dynamic programming’s second form, and the difference is measurable.

# Continuing from the previous blocks: corpus, Counter, memoized, oracle_select and items come from there.
def bottom_up(array, k, s):
    """Builds the same recurrence without recursion; fills every (position, remaining) cell."""
    n = len(array)
    table = [[0] * (k + 1) for _ in range(n + 2)]
    for i in range(n - 1, -1, -1):
        for remaining in range(1, k + 1):
            s.add()
            table[i][remaining] = max(table[i + 1][remaining],
                                      array[i] + table[i + 2][remaining - 1])
    return table[0][k], n * k


s1, s2, s3 = Counter(), Counter(), Counter()
diverging, memo_entries, table_cells = 0, 0, 0
for item in items:
    a, size = memoized(item["array"], PICKS, s1, "full")
    b, cells = bottom_up(item["array"], PICKS, s2)
    oracle_select(item["array"], PICKS, s3)
    if a != b:
        diverging += 1
    memo_entries += size
    table_cells += cells
print("oracle steps        :", s3.steps)
print("memoization steps   :", s1.steps, "| memo entries:", memo_entries)
print("bottom-up steps     :", s2.steps, "| table cells:", table_cells)
print("inputs where they diverge:", diverging, "/ 40")

oracle steps        : 163840
memoization steps   : 2440 | memo entries: 1200
bottom-up steps     : 1440 | table cells: 1440
inputs where they diverge: 0 / 40

The two forms give the same answer on all 40 inputs, but their numbers differ. The bottom-up solution spends 1440 steps, memoization 2440; the difference is the recursive calls themselves. In exchange, memoization holds 1200 entries, bottom-up 1440 cells. That is, per array, memoization holds 30 entries, the table 36 cells.

The trade-off lies exactly here. The bottom-up solution fills every cell — including the ones that are never reachable — and in exchange pays no call overhead. Memoization computes only the subproblems that are actually asked, 30 of 36 cells in this problem, and in exchange pays one call per subproblem. Which one wins depends on how much of the subproblem space is reachable; in this problem, five-sixths of the space is reachable, so bottom-up comes out ahead. As the reachable fraction drops, memoization comes out ahead.

Optimal Substructure Is a Testable Claim

Both forms above use the same recurrence: the best value at a position is whichever is better between skipping that position and moving to the next, or taking that position and moving two ahead. This recurrence’s correctness rests on the optimal substructure assumption, and the assumption is testable — every cell of the recurrence can be asked of the oracle separately.

# Continuing from the previous blocks: corpus, Counter, oracle_select, PICKS and items come from there.
def oracle_suffix(array, start, remaining, s):
    """Finds the suffix's best value by brute force."""
    return oracle_select(array[start:], remaining, s)


cells, matching, s = 0, 0, Counter()
for item in items:
    array = item["array"]
    for i in range(len(array)):
        for remaining in range(1, PICKS + 1):
            cells += 1
            skip = oracle_suffix(array, i + 1, remaining, s)           # i is not selected
            take = array[i] + oracle_suffix(array, i + 2, remaining - 1, s)   # i is selected
            if max(skip, take, 0) == oracle_suffix(array, i, remaining, s):
                matching += 1
print("cells tested:", cells, "| cells where the recurrence matches the oracle:", matching)
print("oracle steps:", s.steps)

cells tested: 1440 | cells where the recurrence matches the oracle: 1440
oracle steps: 1719960

The recurrence matches the oracle on 1440 of 1440 cells. The cost of this test should be noted: 1,719,960 steps, more than a thousand times the solution itself. Testing optimal substructure is more expensive than solving the problem, and this is not surprising — every cell requires solving the suffix from scratch by brute force.

Two things follow from this. First, optimal substructure is not a heuristic but a testable claim; once a recurrence is written, its validity can be asked of the oracle cell by cell. Second, this test is done not in production but during design, on small input. Once the recurrence is validated once, what remains is a solution that runs at 1440 steps on 40 inputs; the million-and-a-half-step test is a one-time cost for that solution’s correctness.

The Second Corpus

# Continuing from the previous blocks: corpus, measure come from there.
for label, seed in (("first corpus (20260218)", 20260218),
                    ("second corpus (20260219)", 20260219)):
    items = corpus(seed)
    print(label)
    for key in ("full", "partial"):
        o = measure(key, items)
        print(f"  key {key:8s} diverging {o['diverging']:2d} / 40 | ratio",
              round(o["diverging"] / 40, 4), "| approach steps", o["approach_steps"],
              "| memo entries", o["memo_entries"])

first corpus (20260218)
  key full     diverging  0 / 40 | ratio 0.0 | approach steps 2440 | memo entries 1200
  key partial  diverging 39 / 40 | ratio 0.975 | approach steps 1000 | memo entries 480
second corpus (20260219)
  key full     diverging  0 / 40 | ratio 0.0 | approach steps 2440 | memo entries 1200
  key partial  diverging 37 / 40 | ratio 0.925 | approach steps 1000 | memo entries 480

The step and memo counts are exactly the same in both corpora: 2440 with 1200, 1000 with 480. This is expected, because these procedures’ steps depend only on the array’s length and the pick limit, not on its values. Partial key’s diverging count drops from 39 to 37; the ratio from 0.9750 to 0.9250. The two-input difference is below the three-input threshold the resolution considers meaningful, and is considered unmeasured. The reading is the same in both corpora: a partial key gives a wrong answer on almost every input.

Summary

• Dynamic programming has two preconditions: optimal substructure and overlapping subproblems; when the first breaks the answer is wrong, when the second breaks the gain disappears.
• In the overlapping structure, calls for n=20 drop from 21,891 to 39; in the non-overlapping structure, the memoized and unmemoized versions both make 39 calls, and the memo holds 19 entries for nothing.
• Full-key memoization spends 67.15 times fewer steps than the oracle and diverges on 0 inputs; the partial-key version spends 163.84 times fewer and diverges on 39 inputs.
• The drop in step count with a partial key is not a speedup but a symptom of error; the memo holds 480 entries instead of 1200, meaning more than half the subproblems are never computed.
• The bottom-up solution spends 1440 steps, fewer than memoization’s 2440, but holds 1440 cells; memoization holds 1200 entries. The winner is decided by how much of the subproblem space is reachable.
• On the second corpus, the step and memo counts are exactly the same; the partial key’s diverging count is 37 instead of 39, and this two-input difference is considered unmeasured.

Next Step

Dynamic programming walked and stored the subproblem space in its entirety. In some problems, the space is so large that walking all of it is not an option; there, the only path is to prove that most of the space contains no solution and cut it. The next lesson measures that cut: pruned search visits 552 nodes on a seven-queens board while unpruned search visits 960,800, and the ratio between the two numbers grows as $n$ grows.