Dynamic Programming | Set 31 (Optimal Strategy for a Game)
There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.
C(i, j) is the maximum sum possible when remaining coins are from i to j. Lets discuss the case when there are remaining coins from i to j (positions) and it’s your turn to pick the coin. Now there are 2 possibilities:
int C[MAX][MAX] = {0};
int x, y, z; //x = C[m+2][n], y = C[m+1][n-1], z = C[m][n-2]
for (int i = 0; i < N; i++) {
for (int m = 0, n = i; n < N; m++, n++) {
//calculate x, y, z
x = (m+2 < N) ? C[m+2][n] : 0;
y = (m+1 < N && n-1 >= 0) ? C[m+1][n-1] : 0;
z = (n-1 > 0) ? C[m][n-2] : 0;
C[m][n] = max(A[m] + min(x,y),
A[n] + min(y,z));
//For Debugging
cout << x << ", " << y << ", " << z << endl;
cout << m << ", " << n << ", " << C[m][n] << endl;
}
}
return C[0][N-1];
}
Also read Dynamic Programming | Set 31 (Optimal Strategy for a Game)
Read full article from Get maximum sum from coins in a line | PROGRAMMING INTERVIEWS
There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.
C(i, j) is the maximum sum possible when remaining coins are from i to j. Lets discuss the case when there are remaining coins from i to j (positions) and it’s your turn to pick the coin. Now there are 2 possibilities:
- You pick coin A(i)
- You pick coin A(j)
F(i, j) represents the maximum value the user can collect from
i'th coin to j'th coin.
F(i, j) = Max(Vi + min(F(i+2, j), F(i+1, j-1) ),
Vj + min(F(i+1, j-1), F(i, j-2) ))
Base Cases
F(i, j) = Vi If j == i
F(i, j) = max(Vi, Vj) If j == i+1
C1 = Ai + min { C(i+2, j), C(i+1, j-1) }
C2 = Aj + min { C(i+1, j-1), C(i, j-2) }
C(i, j) = max { C1, C2 }
= max { Ai + min { C(i+2, j), C(i+1, j-1) },
Aj + min { C(i+1, j-1), C(i, j-2) } }
int maxMoney(int A[], int N) {int C[MAX][MAX] = {0};
int x, y, z; //x = C[m+2][n], y = C[m+1][n-1], z = C[m][n-2]
for (int i = 0; i < N; i++) {
for (int m = 0, n = i; n < N; m++, n++) {
//calculate x, y, z
x = (m+2 < N) ? C[m+2][n] : 0;
y = (m+1 < N && n-1 >= 0) ? C[m+1][n-1] : 0;
z = (n-1 > 0) ? C[m][n-2] : 0;
C[m][n] = max(A[m] + min(x,y),
A[n] + min(y,z));
//For Debugging
cout << x << ", " << y << ", " << z << endl;
cout << m << ", " << n << ", " << C[m][n] << endl;
}
}
return C[0][N-1];
}
Also read Dynamic Programming | Set 31 (Optimal Strategy for a Game)
Read full article from Get maximum sum from coins in a line | PROGRAMMING INTERVIEWS
