3 ms·
I'm not sure that "static" is the appropriate antonym to "dynamic" here. If we set aside the fact that the term "dynamic" was apparently chosen here basically
by HarHarVeryFunny 1y ago
I'm not sure that "static" is the appropriate antonym to "dynamic" here.
If we set aside the fact that the term "dynamic" was apparently chosen here basically because it sounded cool, and for no good reason, and are trying to retroactively redefine it in a way where the word has meaning, then:
With recursion the computation order is predefined and deterministic.
With dynamic programming the computation order is more flexible since the core of the technique is just memoizing prior work. Your DP solution could be organized in recursive top-down fashion, or more optimally in bottom-up fashion if the algorithm is strictly recursive by nature, or neither of the above.
i.e. With dynamic programming in general you are just reusing results if/when they exist, else calculating them - it a more "go with the flow" dynamic approach than recursion where the order of calls is strictly prescribed.
- Certhas 1y agoAgain, if the term linear programming makes sense for linear optimization problems, then the term dynamic makes sense for time dependent ones. Also: the core of dynamic programming is breaking down a global optimization problem into many interacting local pieces. The Bellmann equation, which is the core mathematical result of dynamic programming, features neither recursion nor memoization.
- HarHarVeryFunny 1y agoOK, although that seems to be a different (maybe more thoughtful!) use of the term "dynamic programming". It reminds also of "blackboard-based" AI systems where a bunch of cooperating agents with different capabilities jointly work on a problem by posing sub-problems and sharing them on a common blackboard where other agents can grab them and post a solution back on the board.
- Certhas 1y agoLook at the Wikipedia article on dynamic programming. They are very much related. My impression is that the deep part of the math of dynamic programming, the decomposition into interrelated subproblems, is trivial in the CS text book examples. Then all that's left are implementation aspects.