Once you understand it, dynamic programming is probably the easiest algorithm design technique to apply. In fact, I find that dynamic programming algorithms are often easier to reinvent than to look up in a book.
Of course, for dynamic programming to apply, you must first find the right recursive subdivision of a problem, and that isn't always so easy. Try this one:
Suppose you have a car that gets 10 miles per gallon and a gas tank with a capacity of 10 gallons. You want to drive from Buffalo to Albany on the Thruway starting out with a full tank of gas. There are m possible places to stop for gas on the Thruway and every time you stop for gas, you must entirely fill your gas tank. The two arrays dist[1..m] and price[1..m] are such that:
distk[k] is the distance of stop k from Buffalo. For simplicity, assume each dist[k] is a multiple of 10.
0 < dist[1] < dist[2] < ... < dist[m] < d = total trip distance.
price[k] is the price of gas per gallon at stop k.
There is a way to make the trip without running out of gas.
Suppose that you want to find a sequence of stops that gives your the cheapest trip.
Give a dynamic programming solution to the problem, prove your algorithm produces the optimal result and give the time complexity of your algorithm in terms of d.
7
u/psykotic Apr 05 '10 edited Apr 05 '10
I like Skiena's comment on dynamic programming in his Algorithm Design Manual:
Of course, for dynamic programming to apply, you must first find the right recursive subdivision of a problem, and that isn't always so easy. Try this one: