Problem

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.

思路

• 画搜索图
  • 注意理解的地方. A的第二轮依赖于后手B的决定, 虽然A是先手, 但是B一定得让A获得最少的硬币值
• state:
  • dp[i]表示剩下i个硬币, 先手最后获得的最大价值
• function:
  • 如上图

• initialization:

  • 注意, 要从搜索图中的最下面一行来判断

  • n 是 given array的长度

  • dp[0] = 0

  • dp[1] = num[n - 1]

  • dp[2] = num[n - 1] + num[n - 2]
  • dp[3] = num[n - 2] + num[n - 3] (这步特别容易错)

• for 循环实现

    public boolean firstWillWin(int[] values) {
        if (values == null) return false;

        int n = values.length;
        if (n <= 2) return true;
        if (n == 3) return values[0] + values[1] > values[2];

        int[] dp = new int[n + 1];
        dp[1] = values[n - 1];
        dp[2] = values[n - 1] + values[n - 2];
        dp[3] = values[n - 2] + values[n - 3];

        int sum = values[2] + values[1] + values[0];

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

        return dp[n] * 2 > sum;
    }

• 记忆化搜索实现

    public boolean firstWillWin(int[] values) {
        // write your code here
        int []dp = new int[values.length + 1];
        boolean []flag =new boolean[values.length + 1];
        int sum = 0;
        for(int now : values) 
            sum += now;

        return sum < 2*MemorySearch(values.length, dp, flag, values);
    }
    int MemorySearch(int n, int []dp, boolean []flag, int []values) { 
        if(flag[n] == true)
            return dp[n];
        flag[n] = true;
        if(n == 0)  {
            dp[n] = 0;  
        } else if(n == 1) {
            dp[n] = values[values.length-1];
        } else if(n == 2) {
            dp[n] = values[values.length-1] + values[values.length-2]; 
        } else if(n == 3){
            dp[n] = values[values.length-2] + values[values.length-3]; 
        } else {
            dp[n] = Math.max(
                Math.min(MemorySearch(n-2, dp, flag,values) , MemorySearch(n-3, dp, flag, values)) + values[values.length-n],
                Math.min(MemorySearch(n-3, dp, flag, values), MemorySearch(n-4, dp, flag, values)) + values[values.length-n] + values[values.length - n + 1]
                );
        }

        return dp[n];
    }