Ch.12: Algorithms: Dynamic Programming in Real Code

0:00 You ran dynamic programming this morning. Probably before your first coffee, and definitely without a whiteboard. Bold claim. I didn't reverse a linked list on my way in, so where was it hiding? Did you type git diff today? Obviously. About 20 times before standup. Then you ran it. Let's say the file is 2000 lines and you changed six. Comparing every way those versions could line up would be brutally slow, longer than standup, but the answer comes back before your finger leaves the key. Your spell checker fixing a typo? Same algorithm family.

0:34 Huh. So the topic everyone crams for interviews, panics about, and forgets 2 weeks later is quietly solving a real problem in my terminal. All day long. So today we dig into the one small idea under the scary name, the blowup it prevents, and one team that read the price and walked away. Deal. And the name is half the intimidation, so that gives us our first target. Now, that name comes straight out of 19 fifties defense politics. Richard Bellman, mathematician at RAND, and honestly my favorite naming story in this field.

1:09 It's so good. In his autobiography he says the Secretary of Defense at the time had, and this is a quote, a pathological fear and hatred of the word research. Which is awkward, because research was literally Bellman's job. Right. So he needed a new name for his stage-by-stage decision method, something that sounded impressive and gave nobody ammunition. Programming meant planning back then. And dynamic, in his telling, is a word nobody can use in a negative way. He said it was something not even a Congressman could object to.

1:43 It gets me every time. So the most feared topic on the interview whiteboard was named, at least partly, to survive budget season. The words were real; the fear is just packaging. And the idea underneath starts with a failure. So, the failure first. Take fibonacci, the harmless-looking textbook two-liner, computed the naive recursive way where each call spawns two more. Ask it for 30 and you trigger almost 2.7 million function calls. Now imagine asking for 50: past 40 billion. Wait, billion? For one number?

2:17 Yep. And it's not doing 40 billion different things. It's computing fib of 10, an answer that never changes, over and over and... Again. It's a huge pile of work, but almost none of the questions in it are new. Not deep math, just repetition. You work out an answer, throw it away, and go work it out again. So the fix doesn't have to be deep either; it just has to remember. And the cure for repetition really is familiar: it's caching. Write the answer down the first time you compute it, and every repeat call becomes a lookup.

2:51 The textbook word is memoization, as in memo pad. Python even ships it as a decorator, one line above the function: put functools dot cache on that naive fibonacci and those millions of calls collapse to 31 distinct computations, one per value. Hold on. One decorator does all that, and I don't have to change the function itself? It does. The official docs literally call it memoize, and they demo it on recursive fibonacci. Half of the interview monster is code you've probably already shipped. Okay, but if it's just a cache, why do people find dynamic programming so hard?

3:28 The interview framing is part of it. A tech lead once told me to drill 40 patterns for the next interview loop. That's a test to pass, not a tool to use. But there's a real skill here. Caching is half the idea. The other half is choosing what to cache. Two conditions tell you when that works. So name them, because a cache only earns its keep in specific circumstances. First, the same smaller question has to come up again and again. The textbook calls that overlapping subproblems. For example, one small fibonacci answer hiding inside every larger call above it. Exactly.

4:07 Second, the best answer to the big question has to be built from the best answers to the smaller ones, no take-backs later. That one's called optimal substructure, which sounds fancy but just means the small answers don't lie to you. And if either ingredient is missing? Then the trick buys nothing. Cache a function whose inputs never repeat and you've just, you know, spent memory to feel clever. I mean, that describes a chunk of my Redis bill, honestly. Oh, we've all paid that one. But when both ingredients are there, the blowup flips into a flat bill, every distinct question paid exactly once. Now we cash that in, because nobody ships fibonacci, and this road ends inside your git diff.

4:52 The flagship is a question spell checkers answer constantly: how far apart are two words? Far apart in what unit, though? Single-character edits. Insert one character, delete one, or replace one. The minimum number of those moves to turn one string into the other is called edit distance. Take a word half of us misspell: receive, the one where we type r-e-c-i-e-v-e. Under those three moves, that typo sits exactly two replacements from the correct spelling, so a spell checker can rank the right word as the nearest one.

5:25 Okay. And the brute-force version would be, what, trying every possible sequence of edits? Every insert at every position, every delete, every replacement, and chains of all three. The combinations explode before you finish typing the sentence. Oof. Same shape as the fibonacci mess: a giant search secretly asking tiny questions repeatedly. So the whole job collapses into finding those tiny questions. Let's hear it, then. What's the tiny question for edit distance? Start with the picture. Take a typo like ours and write it down the side of a page, with the correct word across the top.

6:00 Every letter pair gets a little box, and each box holds the answer to one tiny question: the cheapest fix for just the letters up to that point. Okay. One box, one question. And a box never starts from scratch. If its two letters agree, it copies the diagonal box, one step up-left, free of charge. If they clash, it pays for exactly one move and takes the cheapest of the three boxes it can lean on: the one above means a delete, the one to the left means an insert, and that diagonal means a replace.

6:34 Okay, so every box looks at three finished boxes, takes the minimum, done. And that actually costs less? Fill the page corner to corner. The last box, the far corner, is the answer you actually came for: the cheapest way to turn the whole typo into the whole word. Then count the work. Seven letters against seven letters is 49 boxes at three quick looks each, roughly 150 operations. The astronomical search just became lunch money. Which means the spell checker gets to run that on every single word you type.

7:08 And this exact table has a name, right? It's not a party trick. No trick at all. Wagner and Fischer, 1974; the paper's linked below, along with the rest. It proves the whole thing runs in time proportional to the product of the two lengths. Rows times columns, full stop. Same discipline, bigger canvas: that letter grid is secretly what your diff plays on. Imagine two versions of a file. What a diff really wants is the longest common subsequence: the longest set of lines that appear in both versions, in the same order.

7:42 The unchanged skeleton. Right, the spine. Find the spine and the diff writes itself: every old line off the spine is a deletion, every new one that missed it is an insertion. So the red and green lines are just whatever didn't make the skeleton. That's genuinely the whole idea of a diff. And finding that spine uses the same subproblem discipline, rows times columns again: a chunk of the old file against an opening slice of the new one, lines instead of characters. Same grid, bigger pieces. But hang on. Files get big.

8:15 Rows times columns on a hundred-thousand-line file is 10 billion cells, and git doesn't blink. Something else has to be going on. It is. Different algorithm entirely. Eugene Myers, 1986, and your suspicion is the exact observation he built it on. And Myers is the one git ships as its default: the docs list four diff algorithms you can pick from. Its cost formula does something sneaky: it doesn't scale with rows times columns. It scales with the size of the difference. Meaning what, exactly? The bill is roughly the file length times how much actually changed.

8:51 Myers' paper calls it O of ND. N is the combined length; D is how different the two versions turn out to be. You touched six lines out of 2000, so D is tiny and the diff is near-instant. The giant grid never gets built. Okay, but it's still the same question, the same spine, the same don't-ask-twice discipline; Myers just found a cheaper road to the same answer. And that's the part I like: it's a bet on the common case. You almost never diff two unrelated files; you diff yesterday's version against today's.

9:24 And that bet, I think, teaches more than the table does. The textbook grid is the guarantee; Myers is the guarantee plus a wager on what real diffs look like. It's the same instinct that makes Timsort exploit runs of already-sorted data. It really is. And sometimes even the discounted price is too high. Somebody has to look at it and say no. Now the refusal I promised up top. React's core loop is comparing two element trees: the interface you rendered last time versus the one you want now. Trees, not strings.

9:59 Does the grid trick even transfer? There's an exact algorithm family for tree differences, and React's own reconciliation docs put a price on it. Two words gave us a flat page of boxes. Trees aren't flat, and the exact answer prices out a whole dimension higher: on the order of n cubed, for n elements. N cubed? Woah. So let's say 1,000 elements. That would be... ...a billion operations, per update, on the thread that's supposed to keep your UI responsive. A latency nightmare. So the React team, in their own docs, chose not to pay.

10:35 They shipped a heuristic instead, a shortcut rule that's usually right rather than always right, and it runs in O of n. Usually right based on what? Two stated assumptions. Elements of different types produce different trees, so don't compare a div against a video player, just rebuild that branch. And developers mark stable children with a key prop. Wait. So every key warning you've ever scrolled past in a React app was the diff algorithm asking for help. That's exactly what it was. And notice the order of operations: they priced the honest algorithm first, then made the tradeoff in writing.

11:13 The heuristic is a decision, not a guess. So the last job is recognition, because the fear was never really about these tools. It's about seeing the shape inside your own problem. The tell has two parts. The question asks for a count, a minimum, a maximum, or a can-this-be-done. And your honest brute force would try all combinations. Yeah. And when both parts are true, don't reach for a grid yet. Name the smaller question first, in one sentence. I think that sentence is the whole craft, and honestly it's the only part I still slow down for.

11:49 Right, the cell definition. The cost of one prefix against another. The longest spine two files share. Once that sentence exists, everything else is bookkeeping. And you can run it in either direction. Top-down: write the recursion, put the cache on it, let it fill itself in. Bottom-up: fill the grid yourself from the small end. Same answers, same idea, opposite direction. The bottom-up direction is the one that takes a while to trust. Oh, and this one's worth stealing: when each row of the grid only needs the row before it, you keep two rows and throw the rest away.

12:25 Memory problem, gone. Oh, I'm taking that one. And the next time someone defends a nested brute force in code review with, n is small, don't worry, you'll recognize the shape. No catalog of 40 practice problems required. So, two sentences. Never pay twice for the same question. And know what the full answer costs, so you can decide whether to pay at all. Git pays a discounted bill because Myers bet on small changes. React read the n cubed price tag and negotiated down. Same skill both times: reading the price before you buy.

12:59 Which beats whiteboard panic by a mile. The name is fifties politics, the engine is a memo pad, and the craft is that one-sentence subproblem. And next time, since we're finding algorithms hiding in your terminal: why is grep so fast? Searching gigabytes for a string looks like it should be slow, and it absolutely isn't. I already have guesses. Save them. Thanks for listening to Learning Podcasts.