--- title: 'Dynamic Programming' source: 'https://academia.sh/en/courses/advanced-algorithms/dynamic-programming' course: 'Advanced Algorithms and Problem Solving' language: en updated: '2026-08-17T18:07:26+00:00' license: 'CC BY-SA 4.0' --- # Dynamic Programming Memoization's two conditions, both counted: in overlapping subproblems, calls drop from 21,891 to 39, while in non-overlapping ones both stay at 39 and the memo table holds 19 entries for nothing; when the memo's key does not carry the whole state, the approach diverges from the oracle on 39 of 40 inputs. 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. ```python # 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. ```python # 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. ```python # 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. ```python # 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 ```python # 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.