JAVA DP Solution


  • 0
    P
        public boolean PredictTheWinnerDP(int[] nums) {
            int[][] dp = new int[nums.length][nums.length];
            for (int i = 0; i < nums.length; i++) {
                Arrays.fill(dp[i], -1);
            }
    
            int totalSum = 0;
            for (int i = 0; i < nums.length; i++) {
                totalSum += nums[i];
            }
    
            int firstPlayerSum = helperDP(nums, dp, 0, nums.length - 1); 
            int secondPlayerSum = totalSum - firstPlayerSum;
    
            return firstPlayerSum >= secondPlayerSum;
        }
    
        private int helperDP(int[] nums, int[][] dp, int start, int end) {
            if (start > end) {
                return 0;
            }
    
            if (dp[start][end] != -1) {
                return dp[start][end];
            }
    
            int first = nums[start] + Math.min(helperDP(nums, dp, start + 2, end), helperDP(nums, dp, start + 1, end - 1));
            int last = nums[end] + Math.min(helperDP(nums, dp, start + 1, end - 1), helperDP(nums, dp, start, end - 2));
    
            dp[start][end] = Math.max(first, last);
            return dp[start][end];
        }

Log in to reply
 

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