Coins in a Line III

ref: 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?

分析

思路和coins in a line ii一样，特别机智，在dp[i][j]中保存如果只给coins[i,j]第一个选手可以比第二个选手多拿的值，同理，这个值可以是负数。

• 所以状态转移方程就是

  dp[i][j] = max{values[i]-dp[i+1][j], values[j]-dp[i][j-1]}
  

• 初始化

  dp[i][i] = values[i]
  

这个的含义是，对于dp[i][j],可能来自于两个可能，就是拿第i个coin，所以我手里的值加上values[i],这个时候对手就是从dp[i+1][j]里的最大值，因为他也是机智的，所以dp[i][j] = values[i]-dp[i+1][j]. 另一个方向同理

代码

public boolean max(int[] coins) {
    if(coins.length == 0) {
        return false;
    }
    int len = coins.length;
    int sum = IntStream.of(coins).sum();
    int[][] dp = new int[len][len];
    for(int i = 0; i < len; i++) {
        dp[i][i] = coins[i];
    }
    for(int i = 0; i < len; i++) {
        for(int j = i + 1; j < len; j++) {
            dp[i][j] = Math.max(coins[i] - dp[i+1][j], coins[j] - dp[i][j-1]);
        }
    }
    return sum - dp[0][len - 1] < dp[0][len - 1];
}

时间复杂度是O(N^2)

Follow up

follow up是如果有偶数个，能不能一下子做出来