[LeetCode] 486. Predict the Winner

https://leetcode.com/contest/leetcode-weekly-contest-16b/problems/predict-the-winner/

Solution:
Will use dp strategy.Define dp[l][r] as the max gain for one player comparing with his opponent in the range from l to r.

Code:

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