java DP solution with explanation


  • 6
    H

    If the first player choose nums[0], the max he can get is sum( nums )-max[1, end](which is max for the second player). If the first player choose the last element in nums, then the max he can get is sum(nums)-max[0, end-1](which is the max for the second player). Thus, the DP formula is DP[start][end]=Max(sum-dp[start][end-1], sum-dp[start+1][end]).

    One thing I wanna to mention is that, sum in the DP formula is not the total sum for nums, but the sum for nums[start, end].

    public boolean PredictTheWinner(int[] nums) {
            int length = nums.length;
            
            int sum = 0;
            for(int num : nums) sum+=num;
            
            int[][] dp = new int[length][length];
            
            for(int j = 0 ; j< length ; j++)
            {
                int curSum = 0;
                for(int i = j ; i>= 0 ; i--)
                {
                    curSum+=nums[i];
                    if(i == j) dp[i][j]=nums[j];
                    else
                    {
                        dp[i][j]=Math.max(curSum-dp[i][j-1], curSum-dp[i+1][j]);
                    }
                }
            }
            return dp[0][length-1]*2>=sum;
        }
    

Log in to reply
 

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