The core thought of my solution is as follows:
- Assume the array is
[a1, a2, a3, ..., ak] ----- ①
- Player1 picks a1 or ak
- Player2 picks from
[a2, a3, ..., ak] ----- ②
[a1, a2, ..., ak-1] ----- ③
So here comes the sub question, assume we have known the player1's best strategy, when he faced array② or array③. It's easy to find player2 will do what player1 did, because player2 want to win the game too, and he can't find a better strategy.
Now, we can describe the top-down process:
- Player1 has two choice:
s1 = a1 + [player2's strategy when beginning array is ②(because player1's strategy would be use by plalyer2 with beginning array is ①)]
s2 = ak + [player2's strategy when beginning array is③]
what he finally choice is:
s = max(s1, s2)
because he wants win the game, he need the higher score.
- Player2's choice is depend on player1, he has no choice:
if s1 > s2:
rs = player1's strategy when beginning array is ②
rs = player1's strategy when beginning array is ③
I used a bottom-up method to write the codes, first compute the score when length of numbers is 2, then 3, then 4...
class Solution: def PredictTheWinner(self, nums): """ :type nums: List[int] :rtype: bool """ n = len(nums) # initialize a n*n*2 matrix, dp[i][k] means # for beginning array nums[i:k+1], player1's score, # and dp[i][k] means player2's. dp = [[[0 for state in range(2)] for i in range(n)] for j in range(n)] for i in range(n): dp[i][i] = nums[i] for i in range(1, n): #internal from 1 to n-1 for k in range(n-i): # two strategies of player1 p1_1 = nums[k]+dp[k+1][k+i] p1_2 = nums[k+i]+dp[k][k+i-1] if p1_1 > p1_2: dp[k][k+i] = p1_1 dp[k][k+i] = dp[k+1][k+i] else: dp[k][k+i] = p1_2 dp[k][k+i] = dp[k][k+i-1] # player1 win the game if the got the same scores. return dp[n-1] >= dp[n-1]