easy understanding dfs solution


  • 0
    bool PredictTheWinner(vector<int>& nums) 
    {
        return dfs(nums, 0, 0, 1);    
    }
    
    bool dfs(vector<int> nums, int s1, int s2, int player)
    {
        if (nums.size() == 0)
            return (player == 1) ? (s1 >= s2) : (s2 > s1);
        vector<int> numsr = vector<int>(nums.begin() + 1, nums.end());
        vector<int> numsl = vector<int>(nums.begin(), nums.end() - 1);
        if (player == 1)
            return !dfs(numsr, s1 + nums[0], s2, 2) || !dfs(numsl, s1 + nums.back(), s2, 2);
        else
            return !dfs(numsr, s1, s2 + nums[0], 1) || !dfs(numsl, s1, s2 + nums.back(), 1);
    }

Log in to reply
 

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