“Dynamic Programming” is not referring to “computer programming”

Summary

When seeing the phrase “dynamic programming” in an algorithms class or leetcode study guide, the first question people ask is “what does ‘dynamic’ mean in this context?”. The key question is instead “what does ‘programming’ mean in this context?”, because it does not mean “computer programming”. Instead it refers to, as the Oxford English Dictionary puts it, programming. n. 4. Planning carried out for purposes of control, management, or administration. So really, it’s closer to “TV programming” (as in creating a schedule), than “computer programming” (as in writing software). The term was coined in the 1950s at a time when civil engineers would say they’re “programming a new office building” to mean they’re “planning the order and timeline for each sub-step required to construct a new office building”. Ignoring a million details, the resulting plan (the “program”) would be something like Site preparation Excavation Foundation Structural framework Exterior Roofing Interior Hvac/electrical/plumbing Fixtures/furnishing Final inspection (Real engineers can rip this example to shreds in the comments of whichever site they came from.) The steps of the plan must necessarily be in dependency order, because each step likely relies on previous steps be done. Electricians will fail to complete their work if they arrive at the worksite while the loggers are still clearing trees. It shouldn’t need stating, but you wouldn’t pour three separate concrete foundations if you have three steps that need a foundation. You’d do it once so that it’s ready for anything that needs it. That’s the point of ordering the steps. Dynamic Programming in Computer Science similarly means “planning the order of each sub-step required to solve the complete problem”. When “programming” fibonacci(10), the “program” would be something like (given that we already have fib(0) and fib(1) by definition): fib(2) fib(3) fib(4) fib(5) fib(6) fib(7) fib(8) fib(9) fib(10) The steps of the plan must necessarily be...