Day 114, Lintcode, #395, Coins in a Line II

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?

-----------------------------------------------------
方法一
coins表示在i点的最大利益
getTwo表示在i点最大利益是否要取2个coin

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) {
        // write your code here
        int m = values.size();
        if (m < 3) return true;
        
        vector<int> coins(m + 2,0);
        vector<bool> getTwo(m,true);
        
        coins[m - 1] = values[m - 1];
        coins[m - 2] = values[m - 1] + values[m - 2];
        
        for (int i = m - 3; i >= 0; i--) {
            int takeOne = 0, takeTwo = 0;
            // take one
            if (getTwo[i + 1]) {
                takeOne = coins[i + 3] + values[i];
            }else {
                takeOne = coins[i + 2] + values[i];
            }
            
            // take two
            if(getTwo[i + 2]) {
                takeTwo = coins[i + 4] + values[i] + values[i + 1];
            }else {
                takeTwo = coins[i + 3] + values[i] + values[i + 1];
            }
            
            coins[i] = max(takeOne,takeTwo);
            if (takeOne > takeTwo) {
                getTwo[i] = false;
            }
        }
        
        if (getTwo[0]) {
            return coins[0] > coins[2];
        }
        return coins[0] > coins[1];
    }
};

方法二 http://techinpad.blogspot.com/2015/05/lintcode-coins-in-line-ii.html
方法三 http://www.meetqun.com/thread-9798-1-1.html