Description

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], returntrue.

Given A =[1,2,4], return false.

Solution

假设A，B俩人依次拿。A和B每次都能拿1个或者2个。A考虑拿几个的时候是依据怎么拿能让自己得到的value最大，而B接着拿的时候考虑的依据是拿几个才能让A接着拿得到的value最小。由此可以得到状态方程
dp[i] = Math.max( values[i] + Math.min(dp[i + 2], dp[i + 3]), values[i] + values[i + 1] + Math.min(dp[i + 3], dp[i + 4]));

因为状态方程要依据i+4的状态，所以初始状态要把dp[n - 1]到dp[n - 4]都算出来。而且要提前讨论n=1， 2， 3的情况以免溢出。

注意是从左边开始拿，所以从右边开始遍历，并且最后返回结果的时候比对的是dp[0]

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) {
        // write your code here
        if (values == null || values.length == 0) {
            return false;
        }

        int n = values.length;
        if (n == 1 || n == 2) {
            return true;
        }

        int sum = 0;
        for (int value : values) {
            sum += value;
        }

        int[] dp = new int[n];
        dp[n - 1] = values[n - 1];
        dp[n - 2] = values[n - 1] + values[n - 2];
        dp[n - 3] = values[n - 2] + values[n - 3];
        if (n == 3) {
            return dp[n - 3] > sum / 2;
        }

        dp[n - 4] = Math.max(values[n - 4] + Math.min(dp[n - 2], dp[n - 1]), values[n - 4] + values[n - 3]);

        for (int i = n - 5; i >= 0; i--) {
            dp[i] = Math.max(values[i] + Math.min(dp[i + 2], dp[i + 3]), values[i] + values[i + 1] + Math.min(dp[i + 3], dp[i + 4]));
        }

        return dp[0] > sum / 2;
    }
}