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.

Solution:

1. Memory Search DP
2. State: f[i][j] maximal value from i to j
3. Function: f[i][j] = sum[i][j] - min(f[i+1][j], f[i][j-1])
4. Initial: sum[i][j], sum from i to j
5. Answer: sum[0][n-1]/2 < f[0][n-1]

    public boolean firstWillWin(int[] values) {
        if (values == null || values.length == 0) {
            return false;
        }

        int n = values.length;

        int[][] sum = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                sum[i][j] = i == j ? values[i] : sum[i][j-1]+values[j];
            }
        }

        int[][] f = new int[n][n];
        boolean[][] flag = new boolean[n][n];

        return sum[0][n-1]/2 < memorySearch(values, f, sum, flag, 0, n-1);
    }

    private int memorySearch(int[] values, int[][] f, int[][] sum, boolean[][] flag, int l, int r) {
        if (flag[l][r]) {
            return f[l][r];
        }

        flag[l][r] = true;

        if (l > r) {
            f[l][r] = 0;
        } else if (l == r) {
            f[l][r] = values[l];
        } else if (l+1 == r) {
            f[l][r] = Math.max(values[l], values[r]);
        } else {
            int v = Math.min(memorySearch(values, f, sum, flag, l+1, r), 
                            memorySearch(values, f, sum, flag, l, r-1));
            f[l][r] = sum[l][r] - v;
        }

        return f[l][r];
    }