[LintCode] 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?

Example

Given values array A = [1,2,2], return true.

Given A = [1,2,4], return false.

Analysis:
From any index of the array, we should know:

1) the maximum value the first player will get if moving from it.
2) whether it should cover the next index in the move.

With the info, we can construct a DP solution.

class Solution {
public:
    bool firstWillWin(vector<int> &values) {
        // write your code here
        int len = values.size();
        if(len<=2) return true;
        vector<int> maxAGets(len+2, 0),alsoGetNext(len, true);

        maxAGets[len-1] = values[len-1];
        maxAGets[len-2] = values[len-1] + values[len-2];
        
        for(int i=len-3;i>=0;i--)
        {
            //only take i
            int notTakeNext;
            if(alsoGetNext[i+1]) notTakeNext=values[i]+maxAGets[i+3];
            else notTakeNext=values[i]+maxAGets[i+2];
            
            //take i and i+1
            int takeNext, t=values[i]+values[i+1];
            if(alsoGetNext[i+2]) takeNext= t+maxAGets[i+4];
            else takeNext= t+maxAGets[i+3];
            
            maxAGets[i] = max(takeNext, notTakeNext);
            if(takeNext<notTakeNext) alsoGetNext[i] = false;
        }
        if(alsoGetNext[0]) return maxAGets[0] > maxAGets[2];
        return maxAGets[0] > maxAGets[1];
    }
};

Or, a more decent solution:

For any index i, we can know the gap between the two players if the first player moves from it. Suppose the first player moves from i and it wins f[i](the gap). If the second player moves from it, we should consider f[i] as a loss of the first player.

class Solution {
public:
    bool firstWillWin(vector<int> &values) {
        // write your code here
        int size = values.size();
        if(2 >= size) return true;
        vector<int> f(size, 0);
        f[size-1] = values[size-1];
        f[size-2] = values[size-2]+values[size-1];
        
        for(int i = size-3; i >=0; --i)
        {
            f[i] = max(values[i]-f[i+1], values[i]+values[i+1]-f[i+2]);
        }
        return f[0] > 0;
    }
};