486. Predict the Winner

This problem is similar to 464. Can I Win. The difference between this problem and previous problem lie in:

1. In the previous problem, each round player has many choices; while in this prlblem, player has only two choices;
2. In the previous problem, we only need to consider the sum of picked num; while in this problem, we need to consider the sum of two players separately.

In order to solve this problem, we use dp[i][j] to denote the max sum a player can get from nums[i] to nums[j]. Apparently, if player1 picks nums[i] (nums[j]), then dp[i - 1][j] (dp[i][j - 1]) denotes the max sum player2 can get. In other word:

• dp[i][j] = Math.max(sum[i][j] - dp[i + 1][j], sum[i][j] - dp[i][j - 1]) where sum[i][j] is the sum from nums[i] to nums[j]

public boolean PredictTheWinner(int[] nums) {
    if( nums.length == 1 )
        return true;

    int dp[][] = new int[nums.length][nums.length];
    for(int i = 0; i < nums.length; i++) 
        dp[i][i] = nums[i];

    int sum = 0;
    for(int end = 1; end < nums.length; end++) {
        sum = nums[end];
        for(int begin = end - 1; begin >= 0; begin--) {
            sum += nums[begin];
            dp[begin][end] = Math.max(sum - dp[begin + 1][end], sum - dp[begin][end - 1]);
        }   
    }

    return dp[0][nums.length - 1] * 2 >= sum;
}