DP #32. Gold Pot Optimal Strategy - mbhushan/dynpro GitHub Wiki
(32). Gold Pot optimal Strategy.
N pots, each with some number of gold coins, are arranged in a line.
You are playing a game against another player. You take turns picking a
pot of gold. You may pick a pot from either end of the line, remove the pot,
and keep the gold pieces. The player with the most gold at the end wins.
Develop a strategy for playing this game.
Formula:
for (int len=2; len<=size; len++) {
for (int i=0; i<=size-len; i++) {
int j = i + len - 1;
if (T[i+1][j].second + pots[i] > T[i][j-1].second + pots[j]) {
T[i][j].first = T[i+1][j].second + pots[i] ;
T[i][j].second = T[i+1][j].first;
T[i][j].pick = i;
} else {
T[i][j].first = T[i][j-1].second + pots[j];
T[i][j].second = T[i][j-1].first;
T[i][j].pick = j;
}
}
}
|
|
|
|
|
|
|
| Index |
|
0 |
1 |
2 |
3 |
|
|
gold |
3 |
9 |
1 |
2 |
|
| 0 |
3 |
(3,0) |
(9,3) |
(4,9) |
(11,4) |
<- ans |
| 1 |
9 |
|
(9,0) |
(9,1) |
(10,2) |
|
| 2 |
1 |
|
|
(1,0) |
(2,1) |
|
| 3 |
2 |
|
|
|
(2,0) |
|
Gold Pot Strategy
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)