Coins in a Line II 395

Question

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.

Solution

1. 用DP解决。

DP[i]表示从i到end能取到的最大值。

当走到i时，我们有两种选择：

1. 取values[i]的值，则对手可以取values[i+1]的值或者values[i+1]+values[i+2]的值:

1) 对手取values[i+1]的值，我们在之后能取的最大值为DP[i+2]

2) 对手取values[i+1]+values[i+2]的值，我们在之后能取的最大值为DP[i+3]

对手肯定希望最小化我们能取的值，所以我们能取的值是：values1=values[i]+min(DP[i+2],DP[i+3])

1. 取values[i]+values[i+1]的值，则对手可以取values[i+2]的值或者values[i+2]+values[i+3]的值:

1) 对手取values[i+2]的值，我们在之后能取的最大值为DP[i+3]

2) 对手取values[i+2]+values[i+3]的值，我们在之后能取的最大值为DP[i+4]

对手肯定希望最小化我们能取的值，所以我们能取的值是：values1=values[i]+values[i+1]+min(DP[i+3],DP[i+4])

所以，DP[i]的值为max(value1, value2)。

因此我们可以初始化DP最后的几个值，然后倒着回来一直求道DP[0]的值则为我们从0出发能取到的最大值。用所有数的总和减去DP[0]即为对手能取到的值，比较两者大小，若DP[0]更大则我们胜，否则对手胜。

1. 用memory search解。

dp[i][j]表示在i－j区间里我们能取到的最大值。

我们每次能取的值为1个或者2个，因此我们在i－j区间能取的最大值为：i－j区间元素的总和－对手在剩下区间能取到的元素的总和的较小值。但是要注意当区间只有两个或以下元素时，直接取走剩下全部元素即可。因此，状态函数为：

dp[i][j] = sum[i][j] - min(dp[i+1][j], dp[i+2][j]) 当j-i>=2时

dp[i][j] = sum[i][j] 当j-i<2时

注意一定要注意j-i的范围，小心数组越界。

有一点疑惑：一开始用了一种方法，即将数组中从第3个数开始所有位置为3的倍数的数加和的值与剩下其它数加和的值进行比较，若前者大则输，反之则胜，也能得到正确结果。当时考虑的是对手一定能取到位置为3的倍数的数，若这些数之和比其它数之和大则对手一定能胜。

代码如下：

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;
        }

        if(values.length < 3){
            return true;
        }

        int n = values.length;
        int[] DP = new int[n];
        DP[n - 1] = values[n - 1];
        DP[n - 2] = values[n - 2] + values[n - 1];
        DP[n - 3] = values[n - 3] + values[n - 2];

        for(int i = n - 4; i >= 0; i--){
            if(i + 4 >= n){
                DP[i] = Math.max(values[n - 4] + DP[n - 1], values[n - 4] + values[n - 3]);
                continue;
            }
            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])));
        }

        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += values[i];
        }

        if(DP[0] > sum - DP[0]){
            return true;
        }
        return false;
    }
}

memory search

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;
        }

        if(values.length < 3){
            return true;
        }

        int n = values.length;
        int[][] dp = new int[n + 1][n + 1];
        boolean[][] visit = new boolean[n + 1][n + 1];

        int[] sum = new int[n + 1];
        sum[0] = 0;
        for(int i = 1; i <= n; i++){
            sum[i] = sum[i - 1] + values[i - 1];
        }

        return search(1, n, sum, dp, visit) > sum[n] / 2;
    }

    private int search(int start, int end, int[] sum, int[][] dp, boolean[][] visit){
        if(visit[start][end]){
            return dp[start][end];
        }

        if(end - start >= 2){
            dp[start][end] = (sum[end] - sum[start - 1]) - Math.min(search(start + 1, end, sum, dp, visit), search(start + 2, end, sum, dp, visit));
        }else{
            dp[start][end] = sum[end] - sum[start - 1];
        }

        visit[start][end] = true;
        return dp[start][end];
    }
}