Consider a row of n coins of values ... Un, where n is even. A turn...

 

Transcribed Image Text:

Consider a row of n coins of values ... Un, where n is even. A turn based game is being played between 2 players where they alternate turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Give an algorithm to determine the maximum possible amount of money you can definitely win if you move first (assume your opponent will play to maximize the amount they get). Use the idea of dynamic programming in your solution. State a e expression for the run time of your algorithm. Consider a row of n coins of values ... Un, where n is even. A turn based game is being played between 2 players where they alternate turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Give an algorithm to determine the maximum possible amount of money you can definitely win if you move first (assume your opponent will play to maximize the amount they get). Use the idea of dynamic programming in your solution. State a e expression for the run time of your algorithm.