Question

from lintcode
There are n coins in a line. Two players take turns to take a coin from one of the two 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.

Idea

We want to know if the first player can win, i.e. if he can win in the case where

• he tries to get the maximum amount as he can
• the second player tries to minimize his income as possible

/**
 *  maxTotal[left][right] means the maximum amount that the first player
 *  can have.
 *
 *  see calculate() for the dynamic programming function
 */
public class Solution {
    /**
     * @param values: an array of integers
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int[] values) {

        if (values.length == 0) return false;

        int n = values.length;
        int[][] maxTotal = new int[n][n];
        boolean[][] calculated =new boolean[n][n];

        int sum = 0;
        for(int now : values)
            sum += now;

        return sum < 2* calculate(0,values.length - 1, maxTotal, calculated, values);
    }

    int calculate(int left, int right, int [][]maxTotal, boolean [][]calculated, int []values) {

        if(calculated[left][right])
            return maxTotal[left][right];

        calculated[left][right] = true;

        if (left == right) {
            maxTotal[left][right] = values[left];
        } else if(left + 1 == right) {
            maxTotal[left][right] = Math.max(values[left], values[right]);
        } else {

            int  firstPlayerPickLeft = values[left] +
                    // why Math.min? cuz it's opponent's turn, whose goal is to make the first player lose
                    Math.min(
                        // opponent picks left element of the remained list
                        calculate(left + 2, right, maxTotal, calculated, values),
                        // opponent picks right element of the remained list
                        calculate(left + 1, right - 1, maxTotal, calculated, values)
                    );

            int  firstPlayerPickRight = values[right] +
                    // why Math.min? cuz it's opponent's turn, whose goal is to make the first player lose
                    Math.min(
                            // opponent picks left element of the remained list
                            calculate(left, right - 2, maxTotal, calculated, values),
                            // opponent picks right element of the remained list
                            calculate(left + 1, right - 1, maxTotal, calculated, values)
                    );

            maxTotal[left][right] = Math.max(firstPlayerPickLeft, firstPlayerPickRight);
        }

        return maxTotal[left][right];
    }
}