maninbule / leetcodeaccode Goto Github PK

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;
    }
};

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;
    }
};