[leetcode] 486 predict 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

Ideas

1、 Recursive function

• Each time players can only take the leftmost or rightmost , Here, only the scores of the first players are counted , If you get the number, add , If the opponent gets the number, it will decrease
• This can be turned into a typical recursive problem , The first player only takes the optimal solution each time , You can get the final result

2、 Dynamic programming

• Using recursive functions will cause a large number of steps to repeat , It is easy to time out when there is a large amount of data
• Dynamic programming can be used , Use a two-dimensional dp Array
• dp[i][j] Indicates the subscript of the remaining integer i<=x<=j, When i==j Hour means that there is only one integer left to be retrieved
• Every time the subscript is removed i Or subscript j To score , Therefore, we should take the optimal solution in these two cases
• dp[i][j] = max((nums[i]-dp[i+1][j]),(nums[j]-dp[i][j-1]))

# Recursive function 
class Solution(object):
    def PredictTheWinner(self, nums):
        def total(start,end,turn):
            if start == end:
                return nums[start]*turn
            scoreStart = nums[start]*turn + total(start+1,end,turn*-1)
            scoreEnd = nums[end]*turn + total(start, end-1,turn*-1)
            if turn == 1:
                return max(scoreEnd,scoreStart)
            else:
                return min(scoreEnd,scoreStart)
            
        return total(0,len(nums)-1,1) >= 0

# Dynamic programming 
class Solution(object):
    def PredictTheWinner(self, nums):
        n = len(nums)
        dp = [[0 for i in range(n)] for i in range(n)]
        for i in range(n):
            dp[i][i] = nums[i]
        
        for i in range(n-2,-1,-1):
            for j in range(i+1,n):
                dp[i][j] = max((nums[i]-dp[i+1][j]),(nums[j]-dp[i][j-1]))
        return dp[0][n-1]>=0