486. Predict the Winner (Medium)

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.

Example 2:

Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

Note:

1. 1 <= length of the array <= 20.
2. Any scores in the given array are non-negative integers and will not exceed 10,000,000.
3. If the scores of both players are equal, then player 1 is still the winner.

Solution 1: recursion

Explanation
So assuming the sum of the array it SUM, so eventually player1 and player2 will split the SUM between themselves. For player1 to win, he/she has to get more than what player2 gets. If we think from the prospective of one player, then what he/she gains each time is a plus, while, what the other player gains each time is a minus. Eventually if player1 can have a >0 total, player1 can win.

Helper function simulate this process. In each round:
if e==s, there is no choice but have to select nums[s]
otherwise, this current player has 2 options:
--> nums[s]-helper(nums,s+1,e): this player select the front item, leaving the other player a choice from s+1 to e
--> nums[e]-helper(nums,s,e-1): this player select the tail item, leaving the other player a choice from s to e-1
Then take the max of these two options as this player's selection, return it.

version 1: 65ms

class Solution {
    int helper(vector<int>& nums, int s, int e) {
        if (s == e) return nums[s];
        return max(nums[s]-helper(nums, s+1, e), nums[e]-helper(nums, s, e-1));
    }
public:
    bool PredictTheWinner(vector<int>& nums) {
        return helper(nums, 0, nums.size()-1) >= 0;
    }
};

version 2: with cache 3ms

class Solution {
    int helper(vector<int>& nums, int s, int e, vector<vector<int>>& mem) {
        if (mem[s][e] != INT_MAX) return mem[s][e];
        if (s == e) return mem[s][e] = nums[s];
        return mem[s][e] = max(nums[s]-helper(nums, s+1, e, mem), nums[e]-helper(nums, s, e-1, mem));
    }
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> mem(n, vector<int>(n, INT_MAX));
        return helper(nums, 0, n-1, mem) >= 0;
    }
};

Solution 2: iterative 3ms

The dp[i][j] saves how much more scores that the first-in-action player will get from i to j than the second player. First-in-action means whomever moves first. You can still make the code even shorter but I think it looks clean in this way.

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        if(n % 2 == 0) return true;

        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = 0; i < n; ++i) dp[i][i] = nums[i];
        for (int len = 1; len < n; ++len) {
            for (int i = 0; i < n-len; ++i) {
                int j = i+len;
                dp[i][j] = max(nums[i]-dp[i+1][j], nums[j]-dp[i][j-1]);
            }
        }
        return dp[0][n-1] >= 0;
    }
};

Solution 3: DP, Minmax 3ms

class Solution {
    int helper(vector<int>& nums, vector<vector<int>>& dp, int s, int e) {
        if (dp[s][e] != -1) return dp[s][e];
        if (s == e) return dp[s][e] = nums[s];
        if (s+1 == e) return dp[s][e] = max(nums[s], nums[e]);
        return dp[s][e] = max(nums[s]+min(helper(nums, dp, s+2, e), helper(nums, dp, s+1, e-1)), nums[e]+min(helper(nums, dp, s+1, e-1), helper(nums, dp, s, e-2)));
    }
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        // Because if you look at the sum of all the even element S_even and the sum of all the odd elements S_odd, then compare the two sums to decide which elements to take, i.e you can force your opponent to either take all of the even elements or all of the odd element. Hence you can always beet your opponent.
        if(n % 2 == 0) return true;
        vector<vector<int>> dp(n, vector<int>(n, -1));
        return 2*helper(nums, dp, 0, n-1) >= accumulate(nums.begin(), nums.end(),0);
    }
};