https://leetcode.com/problems/predict-the-winner/

Q. Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:

Input:
 [1, 5, 2]

Output:
 False

Explanation:
Initially, player 1 can choose between 1 and 2. If he chooses 2 (or 1), then player 2 can choose
from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. Hence,
player 1 will never be the winner and you need to return False.

Catch: Forsee opponents move

A quick idea may bedp[i][j] = max( dp[i + 1][j] + v[i], dp[i][j - 1] + v[j]), but heredp[i + 1][j]anddp[i][j - 1]are not the values directly available for us, it depends on the move that our opponent make.

Then we assume our opponent is as good as we are and always make optimize move. The worse case is that we will get the minimal value out of all possible situation after our opponent make its move.

so the correct dp formula would bedp[i][j] = max( min (dp[i + 1][j - 1], dp[i + 2][ j]) + v[i], min (dp[i][j - 2], dp[i + 1][ j - 1]) + v[j]}).

Code

import java.util.*;
import java.io.*;
import java.math.*;

public class Solution {

    private int memo(int[] nums, int[][] dp, int i, int j) {
        if (i > j) {
            return 0;
        }
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        dp[i][j] = Math.max(Math.min(memo(nums, dp, i + 1, j - 1), memo(nums, dp, i + 2, j)) + nums[i], Math.min(memo(nums, dp, i + 1, j - 1), memo(nums, dp, i, j - 2)) + nums[j]);
        return dp[i][j];
    }

    public boolean PredictTheWinner(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        int[][] dp = new int[nums.length][nums.length];
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], -1);
        }

        if (2 * memo(nums, dp, 0, nums.length - 1) >= sum) {
            return true;
        }
        return false;
    }
}