# Python 61ms DP solution with explanation

• The core thought of my solution is as follows:

1. Assume the array is
[a1, a2, a3, ..., ak] ----- ①
2. Player1 picks a1 or ak
3. Player2 picks from
[a2, a3, ..., ak] ----- ②
or
[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:

1. 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 ①)]
or
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.
2. Player2's choice is depend on player1, he has no choice:
if s1 > s2:
rs = player1's strategy when beginning array is ②
else:
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][0] means
# for beginning array nums[i:k+1], player1's score,
# and dp[i][k][1] 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][0] = 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][1]
p1_2 = nums[k+i]+dp[k][k+i-1][1]
if p1_1 > p1_2:
dp[k][k+i][0] = p1_1
dp[k][k+i][1] = dp[k+1][k+i][0]
else:
dp[k][k+i][0] = p1_2
dp[k][k+i][1] = dp[k][k+i-1][0]
# player1 win the game if the got the same scores.
return dp[0][n-1][0] >= dp[0][n-1][1]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.