预测玩家
题目大意:
给定一个数组,数组每一位代表一个分数,两个人轮流拿取分数,且只能从剩余分数的两端取,两个人都足够聪明,问第一个人最后的总分能否超过第二个人。
题目解析:
这是一道动态规划的题目,当前数组的最优取值方法,依赖于它的子数组的最优取值方法。定义两个变量:_sum:用来保存前n个分数的总和;_dp:_dp[i][j]用来保存从第i项往前数j个数(包括第i个数),在这j个数组成的子数组中,第一个取值的人最多可以拿多少分。
代码(Python3):
class Solution:
def PredictTheWinner(self, nums: List[int]) -> bool:
if not nums:
return False
if len(nums) == 0:
return True
if len(nums) == 1:
return True
if len(nums) == 2:
return True
_sum = [0] * (len(nums)+1)
_dp = [[0] * (len(nums)+1) for i in range(len(nums))]
_sum[0] = 0
for i in range(1, len(nums)+1):
_sum[i] = _sum[i-1] + nums[i-1]
_dp[1][2] = max(nums[0], nums[1])
for i in range(2, len(nums)):
_dp[i][2] = max(nums[i], nums[i-1])
for j in range(3, len(nums)+1):
if i-j+1 >= 0:
_dp[i][j] = max((_sum[i+1] - _sum[i+1-j]) - _dp[i-1][j-1], (_sum[i+1] - _sum[i+1-j]) - _dp[i][j-1])
if _dp[-1][-1] >= _sum[-1] / 2:
return True
else:
return False
最后是题目的完整描述: