my solution with thinking process


  • 0
    X

    this is a minimax problem

        public boolean PredictTheWinner(int[] nums) {
            int n = nums.length;
            if(n == 0) return true;
            int[][] dp = new int[n][n];
            boolean[][] visited = new boolean[n][n];
            int sum = 0;
            for(int num : nums) sum += num;
            return minimax(sum, 0, n-1, nums, dp, visited) * 2 >= sum;
        }
        
        public int minimax(int sum, int start, int end, int[] nums, int[][] dp, boolean[][] visited){
            if(visited[start][end]) return dp[start][end];
            if(start == end) return nums[start];
            int tmp = Math.max(sum - minimax(sum - nums[start], start + 1, end, nums, dp, visited), sum - minimax(sum - nums[end], start, end - 1, nums, dp, visited));
            visited[start][end] = true;
            dp[start][end] = tmp;
            return tmp;
        }
    }```
    in this kind of problem, dp can be used

Log in to reply
 

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