My JAVA Solution from 60ms to 6ms with recursive and optimalize with dp thought


  • 0
    T

    first I use recursive to solve just easy to think

     /*recursive function each time we will either get left or get right but for one tag is make the result bigger
        so assume the f(i, j) is the result that the number we will win with
        each recursive is to get Max(nums[i]-f(i+1, j), nums[j]-f(i, j-1))*/
        public boolean PredictTheWinner(int[] nums) {
           return getRes(nums, 0, nums.length - 1) >= 0;
        }
        private int getRes(int[] nums, int l, int r) {
            if (l == r) {
                return nums[l];
            }    
            return Math.max(nums[l] - getRes(nums, l + 1, r), nums[r] - getRes(nums, l, r - 1));
        }
    

    but just beat 13% then I thought how to optimalize;we can see in program that the getRes(nums, l + 1, r) and getRes(nums, l, r - 1)for each recursive they should be calculate both ,so we can make a array dp[i][j]which record the form l tor data, and in this way we can avoid calculating repeatly ; this is program:

    public boolean PredictTheWinner(int[] nums) {
            int[][] dp = new int[nums.length][nums.length];
            boolean[][] tag = new boolean[nums.length][nums.length];
            return getRes(nums, 0, nums.length - 1, dp, tag) >= 0;
        }
    
        private int getRes(int[] nums, int l, int r, int[][] dp, boolean[][] tag) {
            if (l == r) {
                return nums[l];
            }
            if (tag[l][r]) {
                return dp[l][r];
            }
            tag[l][r] = true;
            dp[l][r] = Math.max(nums[l] - getRes(nums, l + 1, r, dp, tag), nums[r] - getRes(nums, l, r - 1,dp, tag));
            return dp[l][r];
        }
    

    6ms beat 80%


Log in to reply
 

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