非递归方式
这一题可以通过定义一个矩阵dp,dp[i][j]
表示当原来的nums数组只剩下nums[i:j]
时,选手可以获得的最多的分数。
那么初始情况是:
dp[i][i]=nums[i]
递推公式为:
dp[i][j]=max(sum(nums[i:j])-dp[i][j-1], sum(nums[i:j])-dp[i+1][j])
dp[i][j-1]
和dp[i+1][j]
分别是选择头和尾时,对手可以获得的分数,用sum(nums[i:j])减去对手的分数即为自己的分数。
返回结果为:
分数为dp[0][len(nums)-1]
,对比dp[0][len(nums)-1]*2
和sum(nums)
的大小即可~
代码如下:
class Solution:
def PredictTheWinner(self, nums):
N = len(nums)
dp = [[0]*N for _ in range(N)]
pre_sum = [nums[0]]*(N+1)
# 用prefix sum来降低求sum(nums[i:j])的复杂度
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]
递归方式
Recursion with memory.
class Solution:
def PredictTheWinner(self, nums):
total = sum(nums)
memo = {}
def score(l, r, t):
if l>r: return 0
if (l, r) not in memo:
memo[(l, r)] = t-min(score(l+1, r, t-nums[l]), score(l, r-1, t-nums[r]))
return memo[(l, r)]
sc = score(0, len(nums)-1, total)
return sc>=total-sc