Coins in Line II

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.

Notes:

1. Game DP
2. Think from end to start, reverse thinking
3. State: f[i] represents the maximal amount when i coins left the player can take (first or second player)
4. Function: f[i] = max(sum[n-i-1] - f[i-1], sum[n-i]-f[i-2])
5. Initialize: sum[i] sum when left i coins, f[0] = values[n-1], f[1] = values[n-1] + values[n-2]
6. Answer: f[n-1] > totalSum/2, n-1 represents n coins left, which is the start point, where the first player can take anyway.

Two methods:

1. Classic DP

    public boolean firstWillWin(int[] values) {
        if (values == null || values.length == 0) {
            return false;
        }
   
        if (values.length <= 2) {
            return true;
        }
   
        int n = values.length;
   
        long[] sum = new long[n];
        sum[0] = values[n-1];
        for (int i = 1; i < n; ++i) {
            sum[i] = sum[i-1] + values[n-i-1];
        }
   
        long[] f = new long[n];
        f[0] = values[n-1];
        f[1] = values[n-2] + f[0];
   
        for (int i = 2; i < n; ++i) {
            f[i] = sum[i] - Math.min(f[i-1], f[i-2]);
        }
   
        return f[n-1] > sum[n-1]/2;
    }
   

2. Memory Search

    public boolean firstWillWin(int[] values) {
        if (values == null || values.length == 0) {
            return false;
        }
   
        if (values.length <= 2) {
            return true;
        }
   
        int n = values.length;
   
        long[] sum = new long[n+1];
        sum[0] = 0;
        sum[1] = values[n-1];
        for (int i = 2; i <= n; ++i) {
            sum[i] = sum[i-1] + values[n-i];
        }
   
        long[] f = new long[n+1];
        boolean[] flag = new boolean[n+1];
        return sum[n]/2 < search(n, n, values, sum, f, flag);
    }
   
    private long search(int i, int n, int[] values, long[] sum, long[] f, boolean[] flag) {
        if (flag[i]) {
            return f[i];
        }
        flag[i] = true;
   
        if (i == 0) {
            f[i] = 0;
        } else if (i == 1) {
            f[i] = values[n-1];
        } else if (i == 2) {
            f[i] = values[n-1] + values[n-2];
        } else {
            f[i] = sum[i] - Math.min(search(i-1, n, values, sum, f, flag), search(i-2, n, values, sum, f, flag));
        }
   
        return f[i];
    }