leetcode 486.Predict the Winner

[maninbule]

状态表示：dp[i][j] = {first,second}表示区间[i,j]中，前者最高得first分数，后者最高得second分
状态转移：dp[i][j].first = max(nums[i]+dp[i+1][j].second,nums[j]+dp[i][j-1].second)
dp[i][j].second选对应的first，dp[i+1][j].first or dp[i][j-1].first
状态初始值：dp[i][i] = {nums[i],0}

为什么是nums[i]+dp[i+1][j].second？
因为当前者选了nums[i],后者肯定是dp[i+1][j].first
所以 前者：nums[i]+dp[i+1][j].second，后者：nums[i]+dp[i+1][j].first

我参考的题解视频：https://www.youtube.com/watch?v=WxpIHvsu1RI

typedef pair<int,int> pii;
class Solution {
public:
    //pair<int,int> dp[1010][1010];
    bool PredictTheWinner(vector<int>& nums) {
        vector<vector<pii>> dp(nums.size(), vector<pii>(nums.size())); // 定义一个pair<int,int>类型的二维数组
        int len = nums.size();
        for(int i = 0;i<len;i++)  dp[i][i] = {nums[i],0};
        for(int k = 1;k<len;k++){
            for(int i = 0;i+k<len;i++){
                int j = i+k;
                int sum1 = nums[i]+dp[i+1][j].second,sum2 = nums[j]+dp[i][j-1].second;
                if(sum1 >= sum2) dp[i][j] = {sum1,dp[i+1][j].first};
                else dp[i][j] = {sum2,dp[i][j-1].first};
            }
        }
        return dp[0][len-1].first >= dp[0][len-1].second;
    }
};

另一种改写的方式，把pair{first,second}改成了first-second
状态转移方程dp[i][j] = max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1]),
dp[i][j]为正前者大为负后者大, 其实和上面的代码差不多

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