Answered You can hire a professional tutor to get the answer.
Consider a row of n coins of values V(1)V(n) where n is even. We play a game against an opponent by alternating turns.
Consider a row of n coins of values V(1)···V(n) where n is even. We play a game against an opponent by alternating 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. We consider two ways that the opponent can behave:
(a) Assume the opponent is greedy and always simply chooses the larger of the two coins.
(b) Assume the opponent "plays optimally" and chooses the coin which maximizes the amount of money they can win.
Give a dynamic programming algorithm for cases (a) and (b) to determine the maximum possible amount of money we can definitely win (for the entire game) if we move first.(Hint: Let W[i, j] be the maximum value we can definitely win if it is our turn and only coins i···j, with values V(i)···V(j), remain).
