There is a row of n piles of coins, denoted by a. Two players are alternately making moves which consist of picking a pile on one end of the row and collecting it. Design a strategy for the first player to maximize profit assuming the second player plays optimally.
Solution:
This problem can be solved by using dynamic programming technique. Let F[i,j] be the maximum profit for the first player in the subrow a[i..j]. We can get a recurrence relation F[i,j] = max(a[i] − d[i + 1, j], a[j] − d[i, j − 1]). The running time is O(
It is possible to compute the optimal profit in linear time [1]. The variant on the tree and ring have been studied [2, 3].
Reference: Stackoverflow, IOI 96 A Game
[1] Tomasz Idziaszek, An Optimal Algorithm for Calculating the Profit in the Coins in a Row Game
[2] Deborah E. Seacrest , Tyler Seacrest, “Grabbing the gold,” Discrete Mathematics Volume 312, Issue 10, 28 May 2012, Pages 1804–1806
[3] Josef CibulkaJan KynčlViola MészárosRudolf StolařPavel Valtr, “Solution of Peter Winkler’s Pizza Problem,” International Workshop on Combinatorial Algorithms IWOCA 2009: Combinatorial Algorithms pp 356-367
Algorithms Notes 