## Tuesday, September 20, 2016

### LintCode 396 - Coins in a Line III

https://zhengyang2015.gitbooks.io/lintcode/content/coins_in_a_line_iii_396.html

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
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?

+

dp[i][j] = sum[i][j] - min(dp[i+1][j], dp[i][j-1])。
DFS+Cache
``````    public boolean firstWillWin(int[] values) {
if(values == null || values.length == 0){
return false;
}

int n = values.length;
int[] sum = new int[n + 1];
sum[0] = 0;
for(int i = 1; i <= n; i++){
sum[i] = sum[i - 1] + values[i - 1];
}
int[][] dp = new int[n + 1][n + 1];
boolean[][] visit = new boolean[n + 1][n + 1];

return search(1, n, sum, dp, visit) > sum[n] / 2;
}

private int search(int start, int end, int[] sum, int[][] dp, boolean[][] visit){
if(visit[start][end]){
return dp[start][end];
}

if(start == end){
visit[start][end] = true;
return dp[start][end] = sum[end] - sum[start - 1];
}

int max = (sum[end] - sum[start - 1]) - Math.min(search(start, end - 1, sum, dp, visit), search(start + 1, end, sum, dp, visit));

visit[start][end] = true;
dp[start][end] = max;
return dp[start][end];
}``````

dp题，主要是要推导出公式：
dp[i][j]=max(A[i]+sum[i+1][j]-dp[i+1][j], A[j]+sum[i][j-1]-dp[i][j-1])
A[i]+sum[i+1][j] 和 A[j]+sum[i][j-1]都等于sum[i][j],因此最后公式成为：
dp[i][j]=sum[i][j]-min(dp[i+1][j],dp[i][j-1])

```    public boolean firstWillWin(int[] values) {
int len = values.length;
if (len <= 1) {
return true;
}
int[][] store = new int[len][len];
int[][] sum = new int[len][len];
for (int i = 0; i < len; i++) {
for (int j = i; j < len; j++) {
sum[i][j] = i == j ? values[j] : sum[i][j-1] + values[j];
}
}
for (int i = len - 1; i >= 0; i--) {
for (int j = i; j < len; j++) {
if (i == j) {
store[i][j] = values[i];
} else {
int cur = Math.min(store[i+1][j], store[i][j-1]);
store[i][j] = sum[i][j] - cur;
}
}
}
return store[0][len - 1] > sum[0][len-1] - store[0][len - 1];
}```