승자 예측

정수 배열nums이 제공됩니다. 두 명의 플레이어가 이 배열로 게임을 플레이하고 있습니다: 플레이어 1과 플레이어 2.

플레이어 1과 플레이어 2가 번갈아 가며 플레이어 1이 먼저 시작합니다. 두 플레이어 모두 0의 점수로 게임을 시작합니다. 각 턴에서 플레이어는 배열의 양쪽 끝에서 숫자 중 하나를 가져옵니다(즉, nums[0] 또는 nums[nums.length - 1] ) 배열의 크기를 1 만큼 줄입니다. 플레이어는 선택한 숫자를 점수에 추가합니다. 배열에 더 이상 요소가 없으면 게임이 종료됩니다.

플레이어 1이 게임에서 이길 수 있으면 true를 반환합니다. 두 플레이어의 점수가 같으면 플레이어 1이 여전히 승자이므로 true도 반환해야 합니다. 두 플레이어가 최적의 상태로 플레이하고 있다고 가정할 수 있습니다.

예 1:

입력: 숫자 = [1,5,2]
출력: 거짓
설명: 처음에 플레이어 1은 1과 2 중에서 선택할 수 있습니다.
플레이어 2가 2(또는 1)를 선택하면 플레이어 2는 1(또는 2)과 5 중에서 선택할 수 있습니다. 플레이어 2가 5를 선택하면 플레이어 1은 1(또는 2)만 남게 됩니다.
따라서 플레이어 1의 최종 점수는 1 + 2 = 3이고 플레이어 2는 5입니다.
따라서 플레이어 1은 절대 승자가 되지 않으며 false를 반환해야 합니다.

예 2:

입력: 숫자 = [1,5,233,7]
출력: 참
설명: 플레이어 1은 먼저 1을 선택합니다. 그런 다음 플레이어 2는 5와 7 중에서 선택해야 합니다. 플레이어 2가 어떤 숫자를 선택하든 관계없이 플레이어 1은 233을 선택할 수 있습니다.
마지막으로 플레이어 1은 플레이어 2(12)보다 더 많은 점수(234)를 가지고 있으므로 플레이어 1이 이길 수 있음을 나타내는 True를 반환해야 합니다.

제약:

1 <= nums.length <= 20

0 <= nums[i] <= 107

해결책:

class Solution:
    def canWin(self, nums, i, j, ascore, bscore, aturn):
        if i > j:
            if aturn:
                return ascore >= bscore
            return bscore > ascore
        if aturn:
            return not self.canWin(nums, i + 1, j, ascore + nums[i], bscore, False) or not self.canWin(nums, i, j - 1, ascore + nums[j], bscore, False)
        return not self.canWin(nums, i + 1, j, ascore, bscore + nums[i], True) or not self.canWin(nums, i, j - 1, ascore, bscore + nums[j], True)

    def PredictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)
        return self.canWin(nums, 0, n - 1, 0, 0, True)