1
class Solution:
2
    def PredictTheWinner(self, nums: List[int]) -> bool:
3
        dp = [[-1] * len(nums) for _ in nums]
4

5
        def get_score(i: int, j: int) -> int:
6
            if i == j:
7
                dp[i][j] = 0
8
                return dp[i][j]
9
            if i == j - 1:
10
                dp[i][j] = nums[j] if nums[i] > nums[j] else nums[i]
11
                return dp[i][j]
12
            if dp[i][j] != -1:
13
                return dp[i][j]
14

15
            y1 = get_score(i + 1, j - 1)
16
            y2 = get_score(i + 2, j)
17
            y3 = get_score(i, j - 2)
18
            res_y1 = (
19
                y1 + nums[j] if y1 + nums[j] > y2 + nums[i + 1] else y2 + nums[i + 1]
20
            )
21
            res_y2 = (
22
                y1 + nums[i] if y1 + nums[i] > y3 + nums[j - 1] else y3 + nums[j - 1]
23
            )
24

25
            dp[i][j] = min(res_y1, res_y2)
26
            return dp[i][j]
27

28
        y = get_score(0, len(nums) - 1)
29
        x = sum(nums) - y
30

31
        return 0 if y > x else 1