February 9, 2011 in dynamic programming
There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.
- Would you rather go first or second? Does it matter?
- Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.