Predict the Winner


  • 0

    Click here to see the full article post


  • 0
    J

    I think there is a problem in Approach#4, when the method "winner" called, it does not judge whether the element exists in memo first to avoid recursion.


  • 0

    @Jackie.Snow Thanks for pointing it out. I have updated the code.


  • 1
    B

    For approach #3, the DP table is incorrect. Player 1 is the winner. P1 picks 6, P2 picks 4, P1 picks 2, P2 picks 5, P1 picks 1. In this case both sums are 9 and the problem statement says that if the sums are the same, then P1 is the winner.


  • 1
    W

    For approach #4, code is also wrong. use this code with example '1,5,4' it return false, but right ans should be true;
    the correct code below:
    public boolean PredictTheWinner(int[] nums) {
    int[] dp = Arrays.copyOf(nums,nums.length);
    for (int s = nums.length; s >= 0; s--) {
    for (int e = s + 1; e < nums.length; e++) {
    int a = nums[s] - dp[e];
    int b = nums[e] - dp[e - 1];
    dp[e] = Math.max(a, b);
    }
    }
    return dp[nums.length - 1] >= 0;
    }


  • 0

    @wddtsps
    Agree!
    Would you plz explain more why copy the original array?

        public boolean PredictTheWinner(int[] nums) {
            int[] dp = Arrays.copyOf(nums, nums.length);
            for (int s = nums.length; s >= 0; s--) {
                for (int e = s + 1; e < nums.length; e++) {
                    int a = nums[s] - dp[e];
                    int b = nums[e] - dp[e - 1];
                    dp[e] = Math.max(a, b);
                }
            }
            return dp[nums.length - 1] >= 0;
        }
    

Log in to reply
 

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