Dynamic programming made very little sense to me when I first encountered it, then a few years later I read the DP section of Algorithms by Dasgupta, Papadimitriou, and Vazirani and it somehow clicked for me. Now I enjoy dynamic programming problems when I get them in interviews because they are usually pretty easy once you understand the trick.
back
2 comments
This one is always interesting to me. People mention "dynamic programming" and my gut says "code that writes code" and every single time I remind myself it is just caching earlier calculations. DP is just caching.
DP is just overlapping recursion with caching. That's it.
Richard Bellman just wanted to give a fancy name for mathematical work he was doing without being suspected of it.[1]
[1]https://en.wikipedia.org/wiki/Dynamic_programming#History