LintCode Coins in a line III

focusj 發(fā)布于2019-08-14 15:03 / 1180人閱讀

摘要：復(fù)雜度思路參考的思路，對(duì)于，表示在從到的范圍內(nèi)，先手玩家能拿到的最大的硬幣價(jià)值。對(duì)于狀態(tài)，先手玩家有兩種選擇，要么拿的硬幣，要么拿的硬幣左邊一個(gè)的或者右邊一側(cè)的，如果拿左側(cè)的硬幣，如果拿右側(cè)的硬幣，取兩個(gè)值的最大值。

LintCode 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.

Recursion + Memorization

復(fù)雜度
O(N^2), O(N^2)

思路
參考coins II的思路，對(duì)于dpi，表示在從i到j(luò)的范圍內(nèi)，先手玩家能拿到的最大的硬幣價(jià)值。
對(duì)于狀態(tài)dpi，先手玩家有兩種選擇，要么拿num[i]的硬幣，要么拿num[j]的硬幣(左邊一個(gè)的或者右邊一側(cè)的），
如果拿左側(cè)的硬幣，dpi = num[i] + sumi + 1 - dpi + 1
如果拿右側(cè)的硬幣，dpi = num[j] + sumi - dpi
取兩個(gè)值的最大值。

也可以用dp寫(xiě)。

for(int k = 2; k < len; k ++) {
    for(int i = 0; i < len - k; i ++) {
        int right = i + k;
        dp[i][right] = Math.max();
    }
}

代碼

int len;
Map map = new HashMap<>();

public boolean coins(int[] num) {
    len = num.length;
    int[] sum = new int[len];
    for(int i = 0; i < len; i ++) {
        if(i == 0) sum[i] = num[i];
        else sum[i] = num[i] + sum[i - 1];
    }
    return helper(num, 0, len - 1, sum) * 2 > sum[len - 1];
}

public int helper(int[] num, int left, int right, int[] sum) {
    // base case;
    if(left > right) return 0;
    if(left == right) return num[left];
    if(map.containsKey(left * len + right)) return map.get(left * left + right);
    //
    int val = Math.max(num[left] + getSum(left + 1, right, sum) - helper(num, left + 1, right, sum), num[right] + getSum(left, right - 1, sum) - helper(num, left, right - 1, sum));
    map.put(left * len + right, val);
    return val;
}