C++ DFS+Memorization 0ms


  • 0
    B
    class Solution {
        int maxScore(vector<int>& nums, int start, int end, vector<vector<int>> &m) {
            if(start>end) return 0;
            if(start==end) return nums[start];
            if(m[start][end]) return m[start][end];
            int res1 = nums[start] + min(maxScore(nums, start+2, end, m),maxScore(nums, start+1, end-1, m));
            int res2 = nums[end] + min(maxScore(nums, start, end-2, m), maxScore(nums, start+1, end-1, m));
            m[start][end]=max(res1,res2);
            return m[start][end];
        }
    public:
        bool PredictTheWinner(vector<int>& nums) {
            int sum = accumulate(nums.begin(),nums.end(),0);
            int target = (sum%2)?(sum/2+1):sum/2;
            vector<vector<int>> m(20, vector<int>(20));
            return maxScore(nums, 0, (int)nums.size()-1, m)>=target;
        }
    };
    

Log in to reply
 

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