Evolve from brute force to dp


  • 0
    1. O(2^n) The most intuitive approach is recursion. The sub problem is the max score of the first player. The first player can take either the first or the last element. The best move is the one that leaves the second player the min score.
         bool PredictTheWinner(vector<int>& nums) {
            int sum = accumulate(nums.begin(),nums.end(),0);
            int score = maxScore(0,nums.size()-1,sum,nums);
            return score >= sum -score;
        }
        int maxScore(int begin, int end, int sum, vector<int>& nums) {
            if(begin==end) return nums[begin];
            return sum-min(maxScore(begin+1,end, sum-nums[begin],nums), maxScore(begin,end-1,sum-nums[end],nums));
        }
    
    1. O(2^n) To computer the total score of a player, we have to keep track of the sum of the array. This can be avoided by defining the sub problem as the max score difference. The idea is from @Chidong
        bool PredictTheWinner(vector<int>& nums) {
            return maxScore(0,nums.size()-1,nums) >= 0;
        }
        int maxScore(int begin, int end, vector<int>& nums) {
            if(begin==end) return nums[begin];
            return max(nums[begin]-maxScore(begin+1,end,nums), nums[end]-maxScore(begin,end-1,nums));
        }
    
    1. O(n^2) Memorization
        bool PredictTheWinner(vector<int>& nums) {
            int n = nums.size();
            vector<vector<int>> mem(n,vector<int>(n,INT_MIN));
            return maxScore(0,n-1,nums,mem) >= 0;
        }
        int maxScore(int begin, int end, vector<int>& nums, vector<vector<int>>& mem) {
            if(begin==end) return nums[begin];
            if(mem[begin][end] != INT_MIN) return mem[begin][end];
            return mem[begin][end] = max(nums[begin]-maxScore(begin+1,end,nums,mem), nums[end]-maxScore(begin,end-1,nums,mem));
        }
    
    1. O(n^2) dp and linear space dp.
         bool PredictTheWinner(vector<int>& nums) {
            int n = nums.size();
            vector<vector<int>> mem(n,vector<int>(n));
            for(int i=n-1;i>=0;i--) {
                mem[i][i]=nums[i];
                for(int j=i+1;j<n;j++) mem[i][j] = max(nums[i]-mem[i+1][j],nums[j]-mem[i][j-1]);
            }
            return mem[0][n-1] >= 0;
        }
         bool PredictTheWinner(vector<int>& nums) {
            int n = nums.size();
            vector<int> dp(n);
            for(int i=n-1;i>=0;i--) {
                dp[i] = nums[i];
                for(int j=i+1;j<n;j++) dp[j] = max(nums[i]-dp[j],nums[j]-dp[j-1]);
            }
            return dp[n-1] >= 0;
        } 
    

Log in to reply
 

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