Coins in a Line III

题目：

There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

Could you please decide the first player will win or lose?

分析：

这题目思路跟Coins in a Line II是一样的，但是实现起来并不容易

state: 如果还剩下从i到j的硬币，先取得人可以拿到的最大值是多少？
init: f[i][i] = values[i]
      f[i][i + 1] = max(values[i], values[i + 1]);
假设敌人总是理智的，那么当我们取走start的时候，敌人会拿start + 1或者end
然后导致我们拿到dp[start + 2][end]和dp[start + 1][end - 1]中更小的情况

注意这道题目循环的方式需要稍微改变一下，也不怪归纳为区间类，他的dp矩阵计算方法是从对角线上，一排一排算下去的，更类似区间类，所以循环的方法是

for span from 2 to n
  for i from 0 to n - 1 && j from i + span to n - 1
这也是题目落实过程中的难点之一。

解法：

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;
        }
        int sum = 0;
        vector<vector<int> > dp(n, vector<int>(n, 0) );
        for (int i = 0; i < n; i++) {
            dp[i][i] = values[i];
            sum += values[i];
        }
        for (int i = 0; i < n - 1; i++) {
            dp[i][i + 1] = max(values[i], values[i + 1]);
        }

        for (int span = 2; span < n; span++) {
            for (int i = 0, j = i + span; i < n && j < n; i++, j++) {
                int grab_i = values[i] + min(dp[i + 1][j - 1], dp[i + 2][j]);
                int grab_j = values[j] + min(dp[i][j - 2], dp[i + 1][j - 1]);
                dp[i][j] = max(grab_i, grab_j);
            }
        }

        if (dp[0][n - 1] * 2 < sum) {
            return false;
        }
        return true;
    }
};