Dynamic Programming - Coin In a Line Game Problem | Algorithms

Dynamic Programming - Coin In a Line Game Problem | Algorithms

by SJ · May 8, 2016 Objec­tive: In this game, which we will call the coins-in-a-line game, an even num­ber, n, of coins, of var­i­ous denom­i­na­tions from var­i­ous coun­tries, are placed in a line. Two play­ers, who we will call Alice and Bob, take turns remov­ing one of the coins from either end of the remain­ing line of coins. That is, when it is a player's turn, he or she removes the coin at the left or right end of the line of coins and adds that coin to his or her col­lec­tion. The player who removes a set of coins with larger total value than the other player wins, where we assume that both Alice and Bob know the value of each coin. Exam­ple: coins []  =  { 6, 9, 1, 2, 16, 8} trial 1: (players will pick the best option available for them) coins [] = { 6, 9, 1, 2, 16, 8} , Alice picks 8 coins [] = { 6, 9, 1, 2, 16}, Bob picks 16 coins [] = { 6, 9, 1, 2}, Alice picks 6 coins [] = { 9, 1, 2}, Bob picks 9 coins [] = {1, 2}, Alice picks 2 coins [] = {1}, Bob picks 1 Alice:

Read full article from Dynamic Programming - Coin In a Line Game Problem | Algorithms