LintCode "Coins in a Line II" !

Nice one to learn: DP + Game Theory
https://lefttree.gitbooks.io/leetcode/content/dynamicProgramming2/coinsInLine2.html

In game theory, we assume the other player always take optimal step too. Combining with DP, we put this assumption together with each DP selection.

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) {
        int n = values.size();
    if(n<2) return true;
    
    // Backward DP: since dp[a] -> dp[b] where a > b
    vector<long long> dp(n, 0);
    // init
    dp[n-1] = values[n-1]; // pick 1
    dp[n-2] = values[n-2] + values[n-1]; // pick 2
    
    for(int i = n - 3; i >= 0; i --)
    {
        int dp2 = 0,dp3 = 0, dp4 = 0;
        if(i < n - 4) dp4 = dp[i + 4];
        if(i < n - 3) dp3 = dp[i + 3];
        if(i < n - 2) dp2 = dp[i + 2];
        
        // we pick min because the other player is smart too
        int v1 = values[i] + min(dp2, dp3); // pick 1
        int v2 = values[i] + values[i + 1] + min(dp3, dp4); // pick 2
        dp[i] = max(v1, v2);
    }
    
    long long suma = accumulate(values.begin(), values.end(), 0);
    return dp[0] > (suma - dp[0]);
    }
};