Java 6ms DP solution: get the max total score for first-in-action player


  • 0

    The method getFirstMax returns for each particular input (each subarray, delimited by start and end), the maximum possible total score that the first-in-action player can acquire. This is a set value for each particular input/subarray.

    First, the code:

    class Solution {
        public boolean PredictTheWinner(int[] nums) {
            int[][] memo = new int[nums.length][nums.length];
            int sum = 0;
            for (int i : nums)
                sum += i;
            return 2 * getFirstMax(nums, sum, 0, nums.length - 1, memo) >= sum;
        }
    
        public int getFirstMax(int[] nums, int sum, int start, int end, int[][] memo) {
            if (memo[start][end] > 0)
                return memo[start][end];
            if (start == end)
                return nums[start];
            int res = 0;
            int takeHead = sum - getFirstMax(nums, sum - nums[start], start + 1, end, memo);
            int takeTail = sum - getFirstMax(nums, sum - nums[end], start, end - 1, memo);
            res = Math.max(takeHead, takeTail);
            memo[start][end] = res;
            return res;
        }
    }
    

    At first I tried to solve this with a recursive method that returns boolean which denotes canWin as in most game problems. But I later realized that I have to get a little more numerical for this problem. I decided to design the recursive return value as the maximum possible score available as above, and with memoization added, the solution is done.


Log in to reply
 

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