There is an array of coins with different worth. Two players playing this game can pick a coin from either of the left or right end. The player with maximum sum will win. Both players are optimally playing the game.
If player one wins the game print PLAYER 1 WINS else if player 2 wins print PLAYER 2 WINS if they both have equal sum at the end, print DRAW.
Strategy 1:
Array = {18, 20, 15, 30, 10, 14 }
Player 1 picks 18, now the array of coins is
20 15 30 10 14
Player 2 picks 20, now the array of coins is
15 30 10 14
Player 1 picks 15, now the array of coins is
30 10 14
Player 2 picks 30, now the array of coins is
10, 14
Player 1 picks 14, now the array of coins is
10
Player 2 picks 10.
The total value of coins picked by the second player is more (20 + 30 + 10) compared to the first player (18 + 15 + 14).
So, the second player wins.
Having made the first move, the first player is unable to succeed. So,should we make the first move or not? Does it matter?
Playing first will guarantee that the player will not lose or at least end up with a draw game. Now, consider the strategy 2 using a dynamic programming approach.
Strategy 2:
Considering the same example,
Array = {18, 20, 15, 30, 10, 14}
Since the sum of even coins is more, the first player decides to collect all even coins. He first picks 14, now the other player can only pick a coin (10 or 18). Whichever is picked by the other player, the first player again gets an opportunity to pick an even coin and block all even coins.
@@coding::1@@
Recommended Programs