leetcode486 Predict the Winner

思路：

博弈。

实现：

class Solution 
{
public:
    
    bool PredictTheWinner(vector<int>& nums) 
    {
        int dp[21][21];
        int n = nums.size();
        for (int i = 0; i < n; i++) dp[i][i] = nums[i];
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i + 1; j < n; j++)
            {
                dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1] >= 0;
    }
};