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.


  • 2
    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.


  • 2
    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;
        }
    

  • 0
    C

    @Kara
    If don't copy the original array, the calculation is wrong when "e == s + 1" in the approach #4.
    Such as the example [1, 5, 4], if s=1 and e=2, then dp[e]=dp[2] = max(5-0, 4-0)=5 according to the code, but the right result should be dp[2] = max(5-4, 4-5)=1. So the copy is required for approach #3 and #4.


  • 0
    G

    @bharath4 Agree, for my understanding the result is wrong in approach #3. I've tried to simulate the algorithm on paper with the dp table having the row number as starting index and column number as end index of currently considered subproblem. My result was:

    0  1  2  3  4
    

    0 1 4 -2 6 0
    1 5 3 3 3
    2 2 2 4
    3 4 2
    4 6


  • 0
    G

    Hmm, maybe this time the formatting will be good. Cannot edit the previous post:

      0  1  2  3  4
    

    0 1 4 -2 6 0
    1 5 3 3 3
    2 2 2 4
    3 4 2
    4 6


  • 0
    J

    May I ask why int the first solution we return:
    turn * Math.max(turn * a, turn * b);
    rather than:
    turn * Math.max(a, b);

    I am confused because a and b are computed based on turn and why we need to multiply turn again?


  • 0
    B

Log in to reply
 

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