AM 395. Coins in a Line II

Code(Language:C++) (Judger:cloudjudge-cluster-5)

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
        // 这个DP有些不一般。
        // 1,从后往前。
        // 2,博弈
        const int size = values.size();
        if(size <= 2){
            return true; 
        }
        int sum = 0;
        for(auto i : values){
            sum += i; 
        }
        vector<int> dp(size, 0); // 从该index开始能取得最大值。
        dp[size - 1] = values[size - 1];
        dp[size - 2] = values[size - 2] + values[size - 1];
        dp[size - 3] = values[size - 3] + values[size - 2]; 
        for(int i = size - 4; i >= 0; i--){
            // pick one 
            int pick1 = values[i] + min(dp[i + 2], dp[i + 3]);
            int pick2 = 0; 
            if(i + 4 < size){
               pick2  = values[i] + values[i + 1] + min(dp[i + 3], dp[i + 4]); 
            }
            dp[i] = max(pick1, pick2); 
        }
        return dp[0] > sum / 2; 
        
    }
   
};