Java DP solution with explanation


  • 3
    Y

    We can use dynamic programming. Suppose after several rounds, the remaining array is nums[i], nums[i+1],... nums[j]

    • dp[i][j] = the maximum score of player1 on subarray nums[i..j]

    Player1 can choose either nums[i] or nums[j]. If nums[i] is chosen, player2 will also make best effort to get dp[i+1][j]. So for the subarray nums[i+1] ... nums[j], player1 can get:

    • nums[i + 1] + nums[i + 2] + ... + nums[j] - dp[i+1][j], which is
    • sum(nums[i+1] to nums[j]) - dp[i+1][j]

    So we need another array sum to do range sum query, I set sum[0] to 0, sum[i] is the sum of all elements in nums before index i. so finally:

    • dp[i][j] = max { sum[j+1] - sum[i+1] - dp[i+1][j] + nums[i],
      sum[j] - sum[i] - dp[i][j-1] + nums[j]}
        public boolean PredictTheWinner(int[] nums) {
            if(nums.length <= 2) return true;
            int n = nums.length;
            int[] sum = new int[n+1];
            sum[0] = 0;
            for(int i = 1; i <= n; i ++) {
                sum[i] = sum[i-1] + nums[i-1];
            }
            
            int[][] dp = new int[n][n];
            for(int len = 1; len < n; len ++) {
                for(int i = 0; i + len < n; i ++) {
                    int j = i + len;
                    if(len == 1) dp[i][j] = Math.max(nums[i], nums[j]);
                    else {
                        int can1 = sum[j+1] - sum[i+1] - dp[i+1][j] + nums[i];
                        int can2 = sum[j] - sum[i] - dp[i][j-1] + nums[j];
                        dp[i][j] = Math.max(can1, can2);
                    }
                }
            }
            return sum[n] - dp[0][n-1] <= dp[0][n-1];
        }
        
    

  • 1
    R

    @yuejn93 Some comments with explanation would make your answer even better.


  • 0
    Y

    @rvanga Hi, thanks for the suggestion. I added some explanation, hope it helps.


  • 0
    R

    Hi,I think you can use this to make it clearer.

      int can1 = sum[j+1] - sum[i] - dp[i+1][j];
      int can2 = sum[j+1] - sum[i] - dp[i][j-1];
    

    Because sum[j+1] - sum[i] is the sum of the rest elements, since dp[i+1][j] and dp[i][j-1] is two choices that player 2 can make, the larger one between (sum[j+1] - sum[i] - dp[i+1][j]) and (sum[j+1] - sum[i] - dp[i][j-1]) is the best move player 1 can take.


Log in to reply
 

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