Recursion DP. Short and easy to understand.


  • 0
    M

    DP[i][j] means the max profit a player can get from index i to j. So for any index i to j, the max profit of dp[i][j] will be Max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1]).

        public boolean PredictTheWinner(int[] nums) {
            return (recurse(nums,0,nums.length-1,new int[nums.length][nums.length])>=0);
        }
        public int recurse(int[] nums,int start,int end,int[][] dp){
            if(start==end){
                return nums[start];
            }
            if(dp[start][end]!=0){
                return dp[start][end];
            }
            
            int front=0,back=0;
            front=recurse(nums,start+1,end,dp);
            back=recurse(nums,start,end-1,dp);
            
            dp[start][end]=Math.max(nums[start]-front,nums[end]-back);
            return dp[start][end];
        }
    

Log in to reply
 

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