C++_DP_AC


  • 0
    class Solution {
    public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<pair<int,int>>> dp(n, vector<pair<int,int>>(n));
        for(int i = 0; i < n; ++i){
            dp[i][i] = {nums[i],0};
        }
        for(int len = 2; len <= n; ++len){
            for(int i = 0; i + len <= n; ++i){
                int j = i + len - 1;
                if(dp[i+1][j].second + nums[i] > dp[i][j-1].second  + nums[j]){
                    dp[i][j].first = dp[i+1][j].second + nums[i];
                    dp[i][j].second = dp[i+1][j].first;
                }else{
                    dp[i][j].first = dp[i][j-1].second + nums[j];
                    dp[i][j].second = dp[i][j-1].first; 
                }
            }
        }
        return dp[0][n-1].first >= dp[0][n-1].second;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.