There's a good chance tonight's Advent of Code will require dynamic programming. The difficulty is starting to ramp up, and there's a good chance you won't be able to solve the remaining parts 2 without some clever use of DP and memoization, graphs, etc.
Interesting. I came in contact with dynamic programming as a means to implement the Viterbi algorithm in an equalizer. This relates to calculating “cost” of routes through a trellis, where you accumulate partial results corresponding to alternative routes.
A common misconception by design [1]. The research that was "hidden" behind this innocent-sounding name is very closely tied to the origins of backpropagation in the work of Paul Werbos where it will be further developed as "approximate dynamic programming." Bellman's research is more general and is close to a lot of thinking in physics after Lagrange, indeed quite close to the very notion of a "Lagrangian." Over-simplifying, the question has to do with optimization and guarantees of convergence inside various increasingly less-deterministic processes: how can we provably find true maxima of a given function step-by-step.
[1] In the article, an extract from Bellman's very interesting biography, we read:
"The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research... What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying... Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some com- bination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.”
That is how it is implemented, but the core idea is that a lot of problems can be broken down into subproblems that require shared, repetitive computations to solve, and the table is a way to cache/share those results for each subproblem.
The Change Problem video of Algorithmic Toolbox course on Coursera briefly mentioned about the origins of Dynamic Programming which was wonderful to know. https://www.coursera.org/lecture/algorithmic-toolbox/change-...
There's a good chance tonight's Advent of Code will require dynamic programming. The difficulty is starting to ramp up, and there's a good chance you won't be able to solve the remaining parts 2 without some clever use of DP and memoization, graphs, etc.
[1] https://adventofcode.com/
Interesting. I came in contact with dynamic programming as a means to implement the Viterbi algorithm in an equalizer. This relates to calculating “cost” of routes through a trellis, where you accumulate partial results corresponding to alternative routes.
Isn't dynamic programming just using a table that you fill gradually? So far, all examples of dynamic programming I saw just do that
A common misconception by design [1]. The research that was "hidden" behind this innocent-sounding name is very closely tied to the origins of backpropagation in the work of Paul Werbos where it will be further developed as "approximate dynamic programming." Bellman's research is more general and is close to a lot of thinking in physics after Lagrange, indeed quite close to the very notion of a "Lagrangian." Over-simplifying, the question has to do with optimization and guarantees of convergence inside various increasingly less-deterministic processes: how can we provably find true maxima of a given function step-by-step.
[1] In the article, an extract from Bellman's very interesting biography, we read:
"The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research... What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying... Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some com- bination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.”
That is how it is implemented, but the core idea is that a lot of problems can be broken down into subproblems that require shared, repetitive computations to solve, and the table is a way to cache/share those results for each subproblem.
Here's an early intro from Bellman himself: https://www.ams.org/journals/bull/1954-60-06/S0002-9904-1954...
It gets into continuous problems from section 6 on.