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?

分析：

state: dp[i]表示，在第i个硬币的位置，先出手的人能拿到的最大值。

逻辑是这样的，如果我现在在第i个coin的位置，我拿一个，那么因为对手可以拿1或者2，所以我的value是，
value[i] + dp[i + 2] 或者 value[i] + dp[i + 3]
因为对手是理智的，所以他总是尝试让我的value尽可能小，
于是我拿到grab_one = value[i] + min(dp[i + 2], dp[i + 3])
同样的道理，如果我现在在第i个coin的位置，我拿两个，
于是我拿到grab_two = value[i] + value[i + 1] + min(dp[i + 3], dp[i + 4])。

然后我的策略是尽可能多拿，于是我的dp[i] = max(grab_one, grab_two)。
这道题目，可以初始化只剩下1个，只剩下2个这两种情况，从i = n - 3为下标的地方开始，
因为要考虑到i + 4，所以需要在dp矩阵后面额外再补2个0

解法：

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 n = values.size();
        if (n == 0) {
            return false;
        }
        if (n == 1 || n == 2) {
            return true;
        }

        values.push_back(0);
        values.push_back(0);
        vector<int> res(n + 2, 0);
        res[n - 1] = values[n - 1];
        res[n - 2] = values[n - 1] + values[n - 2];
        int sum = values[n - 1] + values[n - 2];
        for (int i = n - 3; i >= 0; i--) {
            int grab_one = values[i] + min(res[i + 2], res[i + 3]);
            int grab_two = values[i] + values[i + 1] + min(res[i + 3], res[i + 4]);
            res[i] = max(grab_one, grab_two);
            sum += values[i];
        }
        if (res[0] * 2 > sum) {
            return true;
        } else {
            return false;
        }
    }
};