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.


  • 3
    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

  • 0
    J

    The approach#3 is just wrong. For the array mentioned {1, 5, 2, 4, 6}, the first player may pick 6 first, then the second player has to pick 4 or he would lose. Then the first one pick 2, the second picks 5, the first player picks 1, so finally both would be 9, the first one win. Still thanks a lot for your fantastic analysis. The problem is that first you should let dp[i][i] be nums[i], then it works.


  • 0
    B

    Approach #3 solution is error.
    Jjinzhichengche and Bbharath4 are correct.


  • 0
    K

    @jinzhichengche you are right.this is my solution based on your idea.

    class Solution {
        public boolean PredictTheWinner(int[] nums) {
            int len = nums.length;
            int[] dp = new int[len];
            for(int i = len - 2;i >= 0;i--){
                dp[i] = nums[i];
                for(int j = i + 1;j < len;j++)  dp[j] = Math.max(nums[i] - dp[j],nums[j] - dp[j - 1]);
            }
            return dp[len - 1] >= 0;
        }
    }
    

  • 0
    P

    @vinod23 In approach #2, line 9, isn't the condition always true because the array will be initialized with 0 and it will never equal 'null'? To fix this in my solution in C#, I used the nullable types because it would be incorrect to initialize the array with any other value within the valid values of int as that could be a real score. Am I missing something?


  • 0
    S

    @pranjay Since it's an Integer array not int array so all the values will be null at the starting


Log in to reply
 

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