Coins in a Line II

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?

http://www.lintcode.com/en/problem/coins-in-a-line-ii/

Discussion

这个题难就难在它跟Maximum Coins Value那个题状态表示不一样。
f[i]表示从vaules[i]~values[n-1]的最大和。对于the first player来说，有两种选择：

1. select values[i]
2. select values[i] and values[i+1]

在每一种选择下，对方都可以选接下来的一个或者两个硬币，并且迫使第一个player选到的最少。

两种情况下的最大值就是the first player最多得到的values。

Solution

class Solution {
public:
    /**
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    bool firstWillWin(vector<int> &values) {
        if(values.empty()) return false;
        int n = values.size();
        if(n <= 2) return true;
        vector<int> f(n, 0);//f[i]: max accumulated sum from v[n-1]~v[i]
        f[n-1] = values[n-1];
        f[n-2] = values[n-2]+values[n-1];
        f[n-3] = values[n-3]+values[n-2];
        for(int i = n-4; i>=0; i--) {
            //case 1: only values[i] is selected. 
            //Then the other player can selecte values[i+1] or values[i+1] + values[i+2]
            //that is to say, it will be f[i+2] or f[i+3] for the first player
            int case_1 = values[i] + min(f[i+2], f[i+3]);
            //case 2: values[i] and values[i+1] are seleted by the first player
            //similarly the other player can select v[i+2] or value[i+2] + values[i+3]
            int case_2 = values[i] + values[i+1] + min(f[i+3], f[i+4]);
            //update f[i]
            f[i] = max(case_1, case_2);
        }
        int sum = 0;
        for(int i=0; i<n; i++) {
            sum += values[i]; 
        }

        return f[0] > sum-f[0];
    }
};