Dynamic Programming for Technical Interviews
blogarithms.github.io
Dynamic Programming for Technical Interviews
1–10 of 225 posts
Re: Dynamic Programming for Technical Interviews
#2So "DP" is just recursion with memoization? Or an I missing another piece?
Edit: apparently I'm not the only one thinking this: https://news.ycombinator.com/item?id=19395862
Re: Dynamic Programming for Technical Interviews
#3Is dynamic programming the same as memoized recursion, or does it include techniques beyond that?
Re: Dynamic Programming for Technical Interviews
#4I have always felt that dynamic programming is only confusing because of the name. The concept of caching previously calculated values in order to save time by avoiding recalculation (at the cost of using more space) is intuitive.
What am I missing?
Re: Dynamic Programming for Technical Interviews
#5So "DP" is just recursion with memoization? Or an I missing another piece? Edit: apparently I'm not the only one thinking this: https://news.ycombinator.com/item?id=19395862
lol yep and I just made basically the same comment as well.
Re: Dynamic Programming for Technical Interviews
#6So "DP" is just recursion with memoization? Or an I missing another piece? Edit: apparently I'm not the only one thinking this: https://news.ycombinator.com/item?id=19395862
Based on my understanding, the key difference with DP is that you build the solution bottom up instead of top-down.
For example, in case of computing the factorial of 10 recursively, you would start at fact(10) and move down to the base case, fact(1).
With DP, you would start with fact(1) and compute succesive results based on computed ones, all the way up to fact(10).
Following on from this, you usually build up the solution in an array, sequentially, instead of navigating down the tree of solutions and storing as you go (memoization).
Re: Dynamic Programming for Technical Interviews
#7I have always felt that dynamic programming is only confusing because of the name. The concept of caching previously calculated values in order to save time by avoiding recalculation (at the cost of using more space) is intuitive. What am I missing?
Not really much. The only difference is that DP could have smaller cache size if calculation order is planned.
And I agree with you that it's only confusing because of the name.
Re: Dynamic Programming for Technical Interviews
#8Re: Dynamic Programming for Technical Interviews
#9I have always felt that dynamic programming is only confusing because of the name. The concept of caching previously calculated values in order to save time by avoiding recalculation (at the cost of using more space) is intuitive. What am I missing?
Richard Bellman coined the name, and according to legend it was because the phrase 'dynamic programming' was so anodyne that not even the most officious bureaucrat could object.
In Bellman's own words[0]:
"An interesting question is, ‘Where did the name, dynamic programming, come from?’ 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. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. 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—I thought, let’s kill two birds with one stone. 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 combination 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."
-----
0. From http://arcanesentiment.blogspot.com/2010/04/why-dynamic-prog...
Re: Dynamic Programming for Technical Interviews
#10I have always felt that dynamic programming is only confusing because of the name. The concept of caching previously calculated values in order to save time by avoiding recalculation (at the cost of using more space) is intuitive. What am I missing?
Not much. There is the top down and bottom up approach. Classic memoization (top down) needs the full past results to be cached. But sometimes you can save memory by doing it bottom up and only using the previous result of the smaller problem to get the larger problem.
In most interviews you should be good by just doing top down, which is more intuitive. But sometimes the bottom up approach will be the follow up question.