Leetcode 486 题目解答:定义两个二维数组,sum1 和 dp,sum1[i][j] 表示的是 i-j 的总和,dp[i][j] 则表示 i-j 中,先选择的人能获得的最大加和,因为两人需要轮流选择,每人每次都会选择最有利于自己的结果,因此下次选择时,需从前面的总和减去前一组选择可获得的最大值,
- class Solution(object) : def PredictTheWinner(self, nums) : """ :type nums: List[int] :rtype: bool """total = sum(nums) sum1 = [[0
- for i in range(len(nums))]
- for i in range(len(nums))] dp = [[0
- for i in range(len(nums) + 1)]
- for i in range(len(nums) + 1)]
- for i in range(len(nums)) : dp[i][i] = nums[i]
- for i in range(len(nums)) : for j in range(i, len(nums)) : sum1[i][j] = sum(nums[: j + 1]) - sum(nums[: i]) print sum1
- for k in range(1, len(nums)) : for i in range(len(nums) - k) : j = i + k dp[i][j] = max(nums[i] + sum1[i + 1][j] - dp[i + 1][j], nums[j] + sum1[i][j - 1] - dp[i][j - 1])#print dp tmp = dp[0][len(nums) - 1]
- if tmp * 2 >= total: return True
- else: return False
然后再比较先选左边还是先选右边能获得更大的结果,于是可以得到动态转换方程:
dp[i][j] = max(nums[i]+sum1[i+1][j] - dp[i+1][j],nums[j]+sum1[i][j-1]-dp[i][j-1])
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/02-18/17276837.html