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...
Binary search: Video tutorial, Python code and extensions
In its simplest form, binary search is a method for quickly finding a specific target value in a sorted array. It begins by comparing the target value to the middle element of the array. Because the array is sorted, the comparison allows us to determine one-half of the array in which the target cannot lie. The search continues on the remaining half. By doing this repeatedly, we will eventually be left with a search space consisting of a single element, the target value.