Lintcode: Coins in a Line III

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])
比较特别的dp题。game theory。

public class Solution {
    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];
    }
}