Coins in a Line II

Question

There are n coins with different value in a line. Two players take turns to take one or two coins from left side until there are no more coins left. The player who take the coins with the most value wins.

Could you please decide the first player will win or lose?

Example

Given values array A = [1,2,2], return true.

Given A = [1,2,4], return false.

Tags

Dynamic Programming Array Game Theory

Related Problems

Hard Coins in a Line III 30 % Medium Coins in a Line

Analysis

• State:
• dp[i] 现在还剩i个硬币，现在当前取硬币的人最后最多取硬币价值
• Function:
• i 是所有硬币数目
• sum[i] 是后i个硬币的总和
• dp[i] = sum[i]-min(dp[i-1], dp[i-2])
• Intialize:
• dp[0] = 0
• dp[1] = coin[n-1]
• dp[2] = coin[n-2] + coin[n-1]
• dp[n]

``````                  [5, 1, 2, 10] dp[4]
(take 5) /             \ (take 5, 1)
/               \
[1, 2, 10] dp[3]         [2, 10] dp[2]
(take 1) /     \ (take 1, 2)  (take 2) / \ (take 2, 10)
/       \                     /   \
[2, 10] dp[2]  [10] dp[1]     [10] dp[1] [] dp[0]
``````

Solution

``````public class Solution {
/**
* @param values: an array of integers
* @return: a boolean which equals to true if the first player will win
*/
public boolean firstWillWin(int[] values) {
if (values == null || values.length == 0) {
return false;
}
int n = values.length;
int[] dp = new int[n + 1];
boolean[] flag = new boolean[n + 1];

int[] sum = new int[n + 1];
int total = 0;
sum[0] = 0;
for (int i = n - 1; i >= 0; i--) {
sum[n - i] = sum[n - i - 1] + values[i];
total += values[i];
}

return search(n, n, dp, flag, values, sum) > total / 2;
}
public int search(int i, int n, int[] dp, boolean[] flag, int[] values, int[] sum) {
if (flag[i] == true) {
return dp[i];
}
if (i == 0) {
dp[i] = 0;
} else if (i == 1) {
dp[i] = values[n - 1];
} else  if (i == 2) {
dp[i] = values[n - 1] + values[n - 2];
} else {
dp[i] = sum[i] - Math.min(search(i - 1, n, dp, flag, values, sum), search(i - 2, n, dp, flag, values, sum));
}
flag[i] = true;
return dp[i];
}
}
``````