Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins. 

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score. 

Example 1:

Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2. If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. Hence, player 1 will never be the winner and you need to return False.



Example 2:

Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.



Note:

1 
Any scores in the given array are non-negative integers and will not exceed 10,000,000.
If the scores of both players are equal, then player 1 is still the winner.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Complete search

Dynamic programming

Game theory

Mathematics

Data structures

Starter code: class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        

Solutions:
class Solution:

	def PredictTheWinner(self, nums):
		if not nums:
			return True
		n = len(nums)
		if n & 1 == 0:
			return True
		dp = [0] * n
		for i in range(n - 1, -1, -1):
			for j in range(i, n):
				if i == j:
					dp[i] = nums[i]
				else:
					dp[j] = max(nums[i] - dp[j], nums[j] - dp[j - 1])
		return dp[n - 1] >= 0


class Solution:

	def PredictTheWinner(self, nums):
		N = len(nums)
		dp = [[0] * N for _ in range(N)]
		pre_sum = [nums[0]] * (N + 1)
		pre_sum[-1] = 0
		for i in range(1, N):
			pre_sum[i] = pre_sum[i - 1] + nums[i]
		for i in range(N):
			dp[i][i] = nums[i]
		for l in range(1, N):
			for i in range(N - l):
				dp[i][i + l] = max(pre_sum[i + l] - pre_sum[i - 1] - dp[i + 1][i + l], pre_sum[i + l] - pre_sum[i - 1] - dp[i][i + l - 1])
		return dp[0][N - 1] * 2 >= pre_sum[N - 1]


class Solution:

	def PredictTheWinner(self, nums):
		cache = {}

		def whose_turn(i, j):
			return (len(nums) - (j - i + 1)) % 2 == 0

		def traverse(i, j):
			if (i, j) in cache:
				return cache[i, j]
			p1_turn = whose_turn(i, j)
			if i == j:
				return (nums[i], 0) if p1_turn else (0, nums[i])
			if i + 1 == j:
				winning_move = max(nums[i], nums[j])
				losing_move = min(nums[i], nums[j])
				cache[i, j] = (winning_move, losing_move) if p1_turn else (losing_move, winning_move)
				return cache[i, j]
			(p1_left, p2_left) = traverse(i + 1, j)
			(p1_right, p2_right) = traverse(i, j - 1)
			if p1_turn:
				p1_move = max(p1_left + nums[i], p1_right + nums[j])
				p2_move = p2_left if p1_left + nums[i] >= p1_right + nums[j] else p2_right
			else:
				p1_move = p1_left if p2_left + nums[i] >= p2_right + nums[j] else p1_right
				p2_move = max(p2_left + nums[i], p2_right + nums[j])
			cache[i, j] = (p1_move, p2_move)
			return cache[i, j]
		(p1_final, p2_final) = traverse(0, len(nums) - 1)
		return p1_final >= p2_final


class Solution:

	def PredictTheWinner(self, nums):
		memo = [[0 for _ in range(len(nums))] for _ in range(len(nums))]
		self.count = 0

		def winner(left, right, player):
			self.count += 1
			if left == right:
				return player * nums[left]
			if memo[left][right] != 0:
				print(nums[left:right + 1])
				return memo[left][right]
			a = player * nums[left] + winner(left + 1, right, -player)
			b = player * nums[right] + winner(left, right - 1, -player)
			if player == 1:
				res = max(a, b)
			else:
				res = min(a, b)
			memo[left][right] = res
			return res
		self.count = 0
		return winner(0, len(nums) - 1, 1) >= 0


class Solution:

	def PredictTheWinner(self, nums):
		n = len(nums)
		if n == 0:
			return False
		dp = [[0] * n for i in range(n)]
		for i in range(n):
			dp[i][i] = nums[i]
		for period in range(1, n):
			for i in range(n - period):
				j = i + period
				dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])
		return dp[0][n - 1] >= 0


class Solution:

	def PredictTheWinner(self, nums):

		def helper(nums, start, end, mem):
			if start == end:
				return nums[start]
			if (start, end) not in mem:
				mem[start, end] = max(nums[start] - helper(nums, start + 1, end, mem), nums[end] - helper(nums, start, end - 1, mem))
			return mem[start, end]
		return helper(nums, 0, len(nums) - 1, {}) >= 0


class Solution:

	def PredictTheWinner(self, nums):
		dic = {}

		def solve(nums):
			if len(nums) <= 1:
				return sum(nums)
			tnums = tuple(nums)
			if tnums in dic:
				return dic[tnums]
			dic[tnums] = max(nums[0] - solve(nums[1:]), nums[-1] - solve(nums[:-1]))
			return dic[tnums]
		return solve(nums) >= 0


class Solution:

	def PredictTheWinner(self, nums):
		total = sum(nums)
		dic = {}

		def score(i, j, t):
			if i > j:
				return 0
			if (i, j) in dic:
				return dic[i, j]
			ret = max(t - score(i + 1, j, t - nums[i]), t - score(i, j - 1, t - nums[j]))
			dic[i, j] = ret
			return ret
		l = len(nums)
		sc = score(0, l - 1, total)
		return sc >= total - sc


class Solution:

	def PredictTheWinner(self, nums):
		if not nums:
			return 0
		n = len(nums)
		dp = [[0] * n for _ in range(n)]
		for i in range(n):
			dp[i][i] = nums[i]
		for length in range(1, n):
			for i in range(n - length):
				j = i + length
				dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])
		return dp[0][-1] >= 0


class Solution:
	p1dict = {}
	p2dict = {}

	def play1(self, nums):
		if str(nums) in self.p1dict:
			return self.p1dict[str(nums)]
		if len(nums) == 1:
			return nums[0]
		ret = max(self.play2(nums[1:]) + nums[0], self.play2(nums[:-1]) + nums[-1])
		self.p1dict[str(nums)] = ret
		return ret

	def play2(self, nums):
		if str(nums) in self.p2dict:
			return self.p2dict[str(nums)]
		if len(nums) == 1:
			return -nums[0]
		ret = min(self.play1(nums[1:]) - nums[0], self.play1(nums[:-1]) - nums[-1])
		self.p2dict[str(nums)] = ret
		return ret

	def PredictTheWinner(self, nums):
		return self.play1(nums) >= 0


class Solution:

	def PredictTheWinner(self, nums):
		_cache = {}
		return Solution.Moves(self, nums, 0, len(nums) - 1, 1, _cache) >= 0

	def Moves(self, nums, ini, fin, pl, _cache={}):
		memo = str((ini, fin, pl))
		if memo in list(_cache.keys()):
			return _cache[memo]
		if ini == fin:
			if pl == 1:
				_cache[memo] = nums[ini]
				return _cache[memo]
			else:
				_cache[memo] = -nums[ini]
				return _cache[memo]
		else:
			if pl == 1:
				_cache[memo] = max(Solution.Moves(self, nums, ini + 1, fin, 2, _cache) + nums[ini], Solution.Moves(self, nums, ini, fin - 1, 2, _cache) + nums[fin])
				return _cache[memo]
			if pl == 2:
				_cache[memo] = min(Solution.Moves(self, nums, ini + 1, fin, 1, _cache) - nums[ini], Solution.Moves(self, nums, ini, fin - 1, 1, _cache) - nums[fin])
				return _cache[memo]


class Solution:

	def PredictTheWinner(self, nums):
		l = len(nums)
		memo = [[None] * l for _ in range(l)]

		def predict(start, end, memo):
			if start == end:
				return nums[start]
			if memo[start][end]:
				return memo[start][end]
			one = nums[start] - predict(start + 1, end, memo)
			two = nums[end] - predict(start, end - 1, memo)
			memo[start][end] = max(one, two)
			return memo[start][end]
		return predict(0, len(nums) - 1, memo) >= 0