Ask HN: What are good resources for studying Dynamic Programming?
8 comments
Watch Erik Demaine's dynamic programming lectures in this playlist: https://www.youtube.com/playlist?list=PLSX2U_ZE4Huk19DPn34oZ...
I learned a lot from them, he gives a methodology and some rules of thumbs for approaching DP problems, which I found very useful.
I learned a lot from them, he gives a methodology and some rules of thumbs for approaching DP problems, which I found very useful.
CLRS "introduction to algorithms" has a bit on it. Some quite versatile graph algorithms e.g. A* are dynamic programming. From memory some project Euler problems are pretty approachable with dynamic programming, but these are abstract without any applied context.
I had a bit of fun years ago writing search algorithms to find profitable trade routes in Eve online, from memory that was largely based on some strange variation of A*, perhaps you can find some entertaining application like that.
Worth also checking out out some operations research / combinatorial optimisation problems. E.g. one of the simplest problems to tackle with dynamic programming is knapsack.
If you learn linear programming there's also some combinatorial optimisation problems that can be tackled by integrating an LP solver with a custom dynamic programming algorithm. This can be used in a technique called "column generation" where in this context "column" in jargon for a decision variable. You start with an initial set of decision variables and do an LP solve, then get the dynamic programming algorithm to search to find a new variable that can produce a better solution (incorporating information about the prices of constraints from the LP dual solution). Then you plug that new variable (if there is one) as an additional decision variable in the optimisation problem and solve the resulting LP again, getting an improved solution. Then repeat with the new dual prices, iterate until you hit a fixed point. Is applicable for certain problems that can be modelled as LPs where there are very large numbers of decision variables (e.g. > millions) but only a sparse subset are non-zero in a good/optimal solution. I think the classic application of this approach is the "cutting stock" problem.
I had a bit of fun years ago writing search algorithms to find profitable trade routes in Eve online, from memory that was largely based on some strange variation of A*, perhaps you can find some entertaining application like that.
Worth also checking out out some operations research / combinatorial optimisation problems. E.g. one of the simplest problems to tackle with dynamic programming is knapsack.
If you learn linear programming there's also some combinatorial optimisation problems that can be tackled by integrating an LP solver with a custom dynamic programming algorithm. This can be used in a technique called "column generation" where in this context "column" in jargon for a decision variable. You start with an initial set of decision variables and do an LP solve, then get the dynamic programming algorithm to search to find a new variable that can produce a better solution (incorporating information about the prices of constraints from the LP dual solution). Then you plug that new variable (if there is one) as an additional decision variable in the optimisation problem and solve the resulting LP again, getting an improved solution. Then repeat with the new dual prices, iterate until you hit a fixed point. Is applicable for certain problems that can be modelled as LPs where there are very large numbers of decision variables (e.g. > millions) but only a sparse subset are non-zero in a good/optimal solution. I think the classic application of this approach is the "cutting stock" problem.
This is long and thorough, thanks a lot for the writeup!
I found lectures on DP by University of Virginia Prof Abhi Shelat to have best explanation of DP
https://www.youtube.com/playlist?list=PL5ro5yPzj5qDlSYHx9Luz...
http://www.cs.virginia.edu/~shelat/16s-4102/
If you need to understand specific DP problems that are common in competitive programming and interviews, then you should check out Tushar's channel at Youtube
https://www.youtube.com/playlist?list=PLrmLmBdmIlpsHaNTPP_jH...
https://www.youtube.com/playlist?list=PL5ro5yPzj5qDlSYHx9Luz...
http://www.cs.virginia.edu/~shelat/16s-4102/
If you need to understand specific DP problems that are common in competitive programming and interviews, then you should check out Tushar's channel at Youtube
https://www.youtube.com/playlist?list=PLrmLmBdmIlpsHaNTPP_jH...
I second the recommendation of CLRS. Another good source of applied examples is the bioinformatics literature. It may be a little tough if you don't have much background in genetics, but a lot of the basic algorithms in computational biology are essentially dynamic programming algorithms that analyze strings over the alphabets of DNA or amino acids. One of my favorite books, which is a classic and (I think) is pretty approachable for the non-biologist, is Biological Sequence Analysis by Durbin, Eddy, Krogh, and Mitchison.
Practice on online judge helps! You can go to http://codeforces.com/problemset/tags/dp for instance. There are people that could help you also. Just solve and ask if you don't get it. Hope that helps.
Found these useful.
https://people.cs.clemson.edu/~bcdean/dp_practice/
https://people.cs.clemson.edu/~bcdean/dp_practice/
The Needleman/Wunsch algorithm for DNA sequence alignment is a great practical example for learning dynamic programming: https://www.youtube.com/watch?v=vqxc2EfPWdk
I am looking for resources to study dynamic programming, not only theoretical ones, but very practical and example-oriented ones are good as well, actually much better than pure theory.
My focus is to be able to solve algorithmic challenges in contexts such as: competitive programming and coding interviews.
Cheers and thanks for recommending stuff.
----------
EDIT: typos.