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.
... continue reading