share my java DP code


  • 0
    B
    public class Solution {
        public boolean PredictTheWinner(int[] nums) {
            if (nums.length == 1){
                return true;
            }
            int sum = 0;
            for (int i : nums){
                sum += i;
            }
            int n = nums.length;
            int[][] M = new int[n][n];
            for (int j = 0 ; j < n ; j++){
                for (int i = j ; i >= 0 ; i--){
                    if (i == j){
                        M[i][j] = nums[i];
                        continue;
                    }
                    int val1 = i + 1 <= j - 1 ? M[i + 1][j - 1] : 0;
                    int val2 = i + 2 <= j ? M[i + 2][j] : 0;
                    int val3 = i <= j - 2 ? M[i][j - 2] : 0;
                    M[i][j] = Math.max(nums[i] + Math.min(val1, val2), nums[j] + Math.min(val3, val1));
                }
            }
            return 2 * M[0][n - 1] >= sum;
        }
    }
    

Log in to reply
 

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