描述

有 个硬币排成一条线, 第 枚硬币的价值为 .
两个参赛者轮流从任意一边取一枚硬币, 直到没有硬币为止. 拿到硬币总价值更高的获胜.
请判定 第一个玩家 会赢还是会输.

样例

样例 1:

输入: [3, 2, 2]
输出: true
解释: 第一个玩家在刚开始的时候拿走 3, 然后两个人分别拿到一枚 2.
样例 2:

输入: [1, 20, 4]
输出: false
解释: 无论第一个玩家在第一轮拿走 1 还是 4, 第二个玩家都可以拿到 20.

思路：

代表到区间内先手总获益与后手总获益的插值，则

代表了拿走最左和最右分别获益的最大值。具体实现如下。

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)
        {
            return 0;
        }
        vector<vector<int>> dp(n,vector<int>(n,0));
        for(int i=0;i<n;i++)
        {
            dp[i][i]=values[i];
        }
        for(int len=2;len<=n;len++)
        {
            for(int i=0;i<=n-len;i++)
            {
                int j=i+len-1;
                dp[i][j]=max(-dp[i+1][j]+values[i],-dp[i][j-1]+values[j]);
            }
        }
        return dp[0][n-1]>0?true:false;
    }
};