When seeing the phrase \u201cdynamic programming\u201d in an algorithms class\nor leetcode study guide, the first question people ask is \u201cwhat does\n\u2018dynamic\u2019 mean in this context?\u201d.<\/p>\n
The key question is instead \u201cwhat does \u2018programming\u2019 mean in this\ncontext?\u201d, because it does not mean \u201ccomputer programming\u201d.<\/p>\n
Instead it refers to, as the Oxford English Dictionary puts it,<\/p>\n
\nprogramming. n. <\/p>\n
4. Planning carried out for purposes of control, management,\nor administration.<\/strong><\/p>\n<\/blockquote>\n
So really, it\u2019s closer to \u201cTV programming\u201d (as in creating a\nschedule), than \u201ccomputer programming\u201d (as in writing software).<\/p>\n
The term was coined in the 1950s at a time when civil engineers would\nsay they\u2019re \u201cprogramming a new office building\u201d to mean they\u2019re\n\u201cplanning the order and timeline for each sub-step required to construct\na new office building\u201d.<\/p>\n
Ignoring a million details, the resulting plan (the \u201cprogram\u201d) would\nbe something like<\/p>\n
\n
- Site preparation<\/li>\n
- Excavation<\/li>\n
- Foundation<\/li>\n
- Structural framework<\/li>\n
- Exterior<\/li>\n
- Roofing<\/li>\n
- Interior<\/li>\n
- Hvac\/electrical\/plumbing<\/li>\n
- Fixtures\/furnishing<\/li>\n
- Final inspection<\/li>\n<\/ol>\n
(Real engineers can rip this example to shreds in the comments of\nwhichever site they came from.)<\/p>\n
The steps of the plan must necessarily be in dependency order,\nbecause each step likely relies on previous steps be done. Electricians\nwill fail to complete their work if they arrive at the worksite while\nthe loggers are still clearing trees.<\/p>\n
It shouldn\u2019t need stating, but you wouldn\u2019t pour three separate\nconcrete foundations if you have three steps that need a foundation.\nYou\u2019d do it once so that it\u2019s ready for anything that needs it. That\u2019s\nthe point of ordering the steps.<\/p>\n
Dynamic Programming in Computer Science similarly means \u201cplanning the\norder of each sub-step required to solve the complete problem\u201d.<\/p>\n
When \u201cprogramming\u201d
fibonacci(10)<\/code>, the \u201cprogram\u201d would be\nsomething like (given that we already havefib(0)<\/code> and\nfib(1)<\/code> by definition):<\/p>\n\n
fib(2)<\/code><\/li>\nfib(3)<\/code><\/li>\nfib(4)<\/code><\/li>\nfib(5)<\/code><\/li>\nfib(6)<\/code><\/li>\nfib(7)<\/code><\/li>\nfib(8)<\/code><\/li>\nfib(9)<\/code><\/li>\nfib(10)<\/code><\/li>\n<\/ol>\nThe steps of the plan must necessarily be in dependency order,\nbecause each step likely relies on previous steps to be done.\n
fib(7)<\/code> will not be able to get its work done if\nfib(5)<\/code> orfib(6)<\/code> are not ready.<\/p>\nIt shouldn\u2019t need stating, but you wouldn\u2019t compute\n
fib(8)<\/code> three separate times if you have three steps that\nneed it. You\u2019d do it once so that it\u2019s ready for anything that needs it.\nThat\u2019s the point of ordering the steps.<\/p>\nThis \u201cprogram\u201d could be planned top down, i.e. starting with\n
fib(10)<\/code> and determining that you first need to solve\nfib(9)<\/code> andfib(8)<\/code>, and repeating the process\nrecursively.<\/p>\nIt could also be planned bottom up, by noticing the pattern that\nevery fibonacci number will have to be computed in order anyways, so you\nmight as well start from
0<\/code> and work your way up.<\/p>\nEither way, the final plan is the same, and both are considered\nDynamic Programming.<\/p>\n
So next time you see someone struggling to understand what could\npossibly make Dynamic Programming \u201cdynamic\u201d, suggest they instead look\ninto what makes it \u201cprogramming\u201d.<\/p>\n
\nThe term \u201cDynamic Programming\u201d was coined by Richard Bellman in the\n1950s, long before anyone knew how confusing it would become. In his\nautobiography, he describes how he ended up with this name:<\/p>\n
\nThe 1950s were not good years for mathematical research.<\/p>\n
We had a very interesting gentleman in Washington named Wilson. He\nwas Secretary of Defense, and he actually had a pathological fear and\nhatred of the word, research.<\/p>\n
I\u2019m not using the term lightly; I\u2019m using it precisely. His face\nwould suffuse, he would turn red, and he would get violent if people\nused the term, research, in his presence.<\/p>\n
You can imagine how he felt, then, about the term, mathematical.<\/p>\n
The RAND Corporation was employed by the Air Force, and the Air Force\nhad Wilson as its boss, essentially. Hence, I felt I had to do something\nto shield Wilson and the Air Force from the fact that I was really doing\nmathematics inside the RAND Corporation.<\/p>\n
What title, what name, could I choose?<\/p>\n
In the first place I was interested in planning, in decision making,\nin thinking. But planning, is not a good word for various reasons. I\ndecided therefore to use the word, \u201cprogramming\u201d.<\/p>\n
I wanted to get across the idea that this was dynamic, this was\nmultistage, this was time-varying I thought, lets kill two birds with\none stone. Lets take a word that has an absolutely precise meaning,\nnamely dynamic, in the classical physical sense. It also has a very\ninteresting property as an adjective, and that is its impossible to use\nthe word, dynamic, in a pejorative sense. Try thinking of some\ncombination that will possibly give it a pejorative meaning. It\u2019s\nimpossible*.<\/p>\n
Thus, I thought dynamic programming was a good name. It was something\nnot even a Congressman could object to. So I used it as an umbrella for\nmy activities.<\/p>\n<\/blockquote>\n
*This Haskell fan\u2019s contender is \u201cdynamic typing\u201d :P<\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
When seeing the phrase \u201cdynamic programming\u201d in an algorithms class or leetcode study guide, the first question people ask is \u201cwhat does \u2018dynamic\u2019 mean in this context?\u201d. The key question is instead \u201cwhat does \u2018programming\u2019 mean in this context?\u201d, because it does not mean \u201ccomputer programming\u201d. Instead it refers to, as the Oxford English Dictionary … Continue reading “The key to understanding “Dynamic Programming” is that it’s not referring to “computer programming””<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false,"jetpack_publicize_feature_enabled":true},"categories":[23],"tags":[63,64],"class_list":["post-1172","post","type-post","status-publish","format-standard","hentry","category-programming","tag-dynamic-programming","tag-etymology"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1172","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1172"}],"version-history":[{"count":12,"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1172\/revisions"}],"predecessor-version":[{"id":1184,"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1172\/revisions\/1184"}],"wp:attachment":[{"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1172"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1172"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1172"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}