Leetcode 486 Predicting Winners -- dynamic programming + game theory

486. Predicting Winners
     Give you an array of integers nums . The player 1 And players 2 Based on this array, a game is designed .

The player 1 And players 2 Take turns on your own round , The player 1 First of all . At the beginning of the , The initial score of both players is 0 . Every round , Players take a number from either end of the array （ namely ,nums[0] or nums[nums.length - 1]）, The retrieved number will be removed from the array （ Array length minus 1 ）. The number selected by the player will be added to his score . When there are no remaining numbers in the array , Game over .

If the player 1 Can be a winner , return true . If two players score equally , Also think that players 1 Is the winner of the game , Also returned true . You can assume that each player's play will maximize his score .

Example 1：

Input ：nums = [1,5,2]
Output ：false
explain ： In limine , The player 1 It can be downloaded from 1 and 2 To choose from .
If he chooses 2（ perhaps 1 ）, So players 2 It can be downloaded from 1（ perhaps 2 ） and 5 To choose from . If the player 2 I chose 5 , So players 1 Only 1（ perhaps 2 ） Optional .
therefore , The player 1 The final score is 1 + 2 = 3, And players 2 by 5 .
therefore , The player 1 Will never be a winner , return false .
Example 2：

Input ：nums = [1,5,233,7]
Output ：true
explain ： The player 1 First choice 1 . And then the players 2 Must be from 5 and 7 To choose from . No matter the players 2 Choose which , The player 1 You can choose 233 .
Final , The player 1（234 branch ） Compare players 2（12 branch ） Get more points , So back true, It means the player 1 Can be a winner .

Tips ：

1 <= nums.length <= 20
0 <= nums[i] <= 107

Answer key

Game theory problems , well , Let's deal with it directly by dynamic programming , We define two arrays dp[0] and dp[1] It means the player 1 And players 2 The maximum score you can get , Finally, judge whose score is big .

AC Code

class Solution {
    
public:
    int dp[25][25][2];//dp[][][0] It means the player 1 My biggest score ,dp[][][1] It means the player 2 My biggest score 
    bool PredictTheWinner(vector<int>& nums) 
    {
    
        memset(dp,0,sizeof(dp));
        for(int i=nums.size();i>=1;i--)
        {
    
            for(int j=i;j<=nums.size();j++)
            {
    
                dp[i][j][0] = max(-dp[i+1][j][1] + nums[i-1],-dp[i][j-1][1]+nums[j-1]);
                dp[i][j][1] = max(-dp[i+1][j][0] + nums[i-1],-dp[i][j-1][0]+nums[j-1]);
            }
        }
        return dp[1][nums.size()][0]>=0;// Because players 1 First of all , Finally, just judge the player 1 Whether the score obtained is greater than or equal to 0 that will do 
    }
};