**The core thought of my solution is as follows:**

- Assume the array is

[a_{1}, a_{2}, a_{3}, ..., a_{k}] ----- ① - Player1 picks a
_{1}or a_{k} - Player2 picks from

[a_{2}, a_{3}, ..., a_{k}] ----- ②

or

[a_{1}, a_{2}, ..., a_{k-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:

s_{1}= a_{1}+ [player2's strategy when beginning array is ②(because player1's strategy would be use by plalyer2 with beginning array is ①)]

or

s_{2}= a_{k}+ [player2's strategy when beginning array is③]

what he finally choice is:

s = max(s_{1}, s_{2})

because he wants win the game, he need the higher score. - Player2's choice is depend on player1, he has no choice:

if s_{1}> s_{2}:

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]
```