Coins in a Line III
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.
Could you please decide the first player will win or lose?
Example Given array A = [3,2,2], return true.
Given array A = [1,2,4], return true.
Given array A = [1,20,4], return false.
Challenge
Follow Up Question:
If n is even. Is there any hacky algorithm that can decide whether first player will win or lose in O(1) memory and O(n) time?
解题思路：和II类似
dp[left][right]表示从left到right所能取到的最大值
/**
* @param values: a vector of integers
* @return: a boolean which equals to true if the first player will win
*/
boolean firstWillWin(int[] values) {
int n = values.length;
// calcualte the total sum for sub-array i to j
int[][] total = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
total[i][j] = values[j] + (i == j ? 0 : total[i][j - 1]);
}
}
//calculate the max value a player can get in sub-array i to j
int[][] dp = new int[n][n];
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
if (i + k >= n) {
break;
}
if (k == 0) {
dp[i][i] = values[i];
} else {
int take_left = values[i] + (total[i + 1][i + k] - dp[i + 1][i + k]);
int take_right = values[i + k] + (total[i][i + k - 1] - dp[i][i + k - 1]);
dp[i][i + k] = Math.max(take_left, take_right);
}
}
}
return 2 * dp[0][n - 1] > total[0][n - 1];
}
boolean firstWinEvenCoins(int[] values) {
int sum = 0;
int odd_sum = 0;
int even_sum = 0;
for (int i = 0; i < values.length; ++i) {
sum += values[i];
if (i % 2 == 0) {
odd_sum += values[i];
} else {
even_sum += values[i];
}
}
return odd_sum != even_sum;
}