Lintcode 396. 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.

Challenge

Follow Up Question:

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?

Solution 1: DFS + Memo
dp[i][j] means the interval [i, j] the max diff between the two players.

Code (Java):

public class Solution {
    /**
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int[] values) {
        int n = values.length;
        
        int[][] memo = new int[n][n];
        
        return firstWillWinHelper(values, 0, n - 1, memo) > 0;
    }
    
    private int firstWillWinHelper(int[] values, int start, int end, int[][] memo) {
        if (memo[start][end] != 0) {
            return memo[start][end];
        }
        
        if (start == end) {
            memo[start][end] = values[start];
            return memo[start][end];
        }
        
        int maxDiff = Math.max(values[start] - firstWillWinHelper(values, start + 1, end, memo), 
                               values[end] - firstWillWinHelper(values, start, end - 1, memo));
        memo[start][end] = maxDiff;
        
        return maxDiff;
    }
}

Solution 2: DP

Code(Java):

public class Solution {
    /**
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int[] values) {
        int n = values.length;
        int[][] dp = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            dp[i][i] = values[i];
        }
        
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = Math.max(values[i] - dp[i + 1][j], values[j] - dp[i][j - 1]);
            }
        }
        
        return dp[0][n - 1] > 0;
    }
}

Update on 8/27/21:

 public class Solution {
    /**
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int[] values) {
        // write your code here
        if (values == null || values.length == 0) {
            return false;
        }
        
        if (values.length == 1) {
            return true;
        }
        
        // dp[i][j] means the max score difference between the current player and the other player
        // for the values [i, j]
        int n = values.length;
        int[][] dp = new int[n][n];
        
        // init
        for (int i = 0; i < values.length; i++) {
            dp[i][i] = values[i];
        }
        
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Math.max(values[i] - dp[i + 1][j], values[j] - dp[i][j - 1]);
            }
        }
        
        return dp[0][n - 1] >= 0;
    }
}

public class Solution {
    /**
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int[] values) {
        // write your code here
        if (values == null || values.length == 0) {
            return false;
        }

        int n = values.length;
        int[][] memo = new int[n][n];

        firstWillWinHelper(values, 0, n - 1, memo);

        return memo[0][n - 1] > 0 ? true : false;
    }

    private void firstWillWinHelper(int[] values, int start, int end, int[][] memo) {
        if (start > end) {
            return;
        }

        if (memo[start][end] != 0 ) {
            return;
        }

        if (start == end) {
            memo[start][end] = values[start];
            return;
        }

        firstWillWinHelper(values, start + 1, end, memo);
        firstWillWinHelper(values, start, end - 1, memo);

        memo[start][end] = Math.max(values[start] - memo[start + 1][end], 
                                    values[end] - memo[start][end - 1]);
    }
}