Java recursive solution, very easy to understand


  • 0
    Y

    I think the code is rather self explanatory: for player1 to win, at each turn, player1 chooses either left or right, and no matter what player2 chooses, player1 has to have a better score.
    I feel no need for DP in this solution - please correct me if wrong.

    public class Solution {
        public boolean PredictTheWinner(int[] nums) {
            return helper(nums, 0, nums.length-1, 0, 0);
        }
        private boolean helper(int[] nums, int left, int right, int score1, int score2) {
            if (left > right) return score1 >= score2;
            if (left == right) return score1 + nums[left] >= score2; // player1 starts first
            return helper(nums, left+1, right-1, score1 + nums[left], score2 + nums[right]) &&
                   helper(nums, left+2, right, score1 + nums[left], score2 + nums[left + 1]) ||
                   helper(nums, left+1, right-1, score1 + nums[right], score2 + nums[left]) &&
                   helper(nums, left, right-2, score1 + nums[right], score2 + nums[right-1]);
        }
    }
    

Log in to reply
 

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