Since examples are the best way to go understand dynamic programming, here are three more classic dynamic programming problems. Make sure you either solve the each problem or try at least for a few hours before reading the solution.
Counting paths in a grid
You have a rectangular grid of points with n rows and n columns. You start at the bottom left corner. At each step, you can either go up to the next point in the same column or right to the next point in the same row. How many such paths are there from the bottom left corner to the top right corner?
What if some points are deleted (that is, no path ca...