How to Describe a Dynamic Program in a Paper

Now today I’d like to talk about a bit of a pet peeve of mine and I guess it’s maybe more of an opinion than usual, or at least it’s something stylistic: how to describe a dynamic program.

Sometimes people immediately come at you with a table and how you would loop over it; where to look and what to write – and, I mean, it’s not wrong. If you describe this well, I’ll understand it. But it’s an implementation detail, right? You’re kind of starting the story in the middle there. What I really want to know is: “why is this correct;” not “how I would program it.”

So what you do, is you define a function – let’s call it $f$ – that takes an instance and possibly some extra restrictions, and then you define the value of $f$ to be the optimum on this instance, under these restrictions. Like, what is the maximum value you can get in this knapsack instance if you can only use the first $i$ items and weight at most $w$. This is a well-defined function even before you talk about how to compute it, and having a name for it is super helpful, just grammatically, in talking about correctness. Because now you can start proving mathematical identities that hold for $f$. We’re not in the weeds of a sequential algorithm that’s pushing numbers around, we’re making static observations about $f$ that you can prove in isolation. Incidentally, it also forces you to be explicit about what the values in your eventual table actually mean. This is something that’s quite easy to be a little bit too handwavey about if you just spin a yarn about numbers in tables.

On a more formal level, there’s the so-called “optimal substructure property,” but I’ll let you look that up on your own – and I don’t usually find it necessary to call it out by name. I have a much longer video specifically about the Knapsack problem where I describe a dynamic program in the way I’ve sketched above. There’s a couple of things it would do a bit differently if I made it again, but I think it came out pretty well.