1. 预测赢家（leetcode 486. Predict the Winner）
中文链接：https://leetcode-cn.com/problems/predict-the-winner/ 英文链接：https://leetcode.com/problems/predict-the-winner/
题目：
我们可以分成两种情况来考虑，当这个数组数目是偶数时，先手是必胜的。在选择同样数目的数字时，先手可以选择加和更大的组合； 对于总数目是奇数的情况，我们可以构建一个二维数组dp，来存放第i到j位置的这些数字先手和后手的得分差值。比如说，对于示例2，当i=0, j=0时，只有一种选择，也就是先手拿1，差值为1，dp[0][0] = 1；当i=0, j = 1时，数组为[1,5]，先手拿5，后手拿1，差为4，dp[0][1] = 4；....... 那么，在dp[i][j]位置的值是什么呢？ 假如先手拿nums[i]，那么与后手的差就是nums[i] - dp[i 1][j]；先手拿nums[j]，那么与后手的差即nums[j] - dp[i][j-1]。以下是python实现：
代码语言：javascript复制class Solution:
def PredictTheWinner(self, nums: List[int]) -> bool:
n = len(nums)
if not n % 2:
return True
dp = [[0 for x in range(n)] for y in range(n)]
for i in range(n):
dp[i][i] = nums[i]
for i in range(n-2, -1, -1):
for j in range(i 1, n):
dp[i][j] = max(nums[i] - dp[i 1][j], nums[j] - dp[i][j-1])
return dp[0][-1]>=02. 打家劫舍 II （213. House Robber II）
中文链接：https://leetcode-cn.com/problems/house-robber-ii/ 英文链接：https://leetcode.com/problems/house-robber-ii/
image.png
打家劫舍的进阶版题型。不能同时选首位和末尾数字。所以这里可以构建一个n行两列的数组，第一列表示第一个数字而不选最后一个，第二列表示选择最后一个数。其他的地方与打家劫舍I一样。python实现：
代码语言：javascript复制class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
if n <= 3:
return max(nums)
else:
dp = [[0,0] for x in range(n)]
dp[0][0],dp[1][0] = nums[0], max(nums[0], nums[1])
dp[1][1], dp[2][1] = nums[1], max(nums[1], nums[2])
for i in range(2, n - 1):
dp[i][0] = max(dp[i-2][0] nums[i], dp[i-1][0])
dp[i 1][1] = max(dp[i-1][1] nums[i 1], dp[i][1])
return max(dp[-1][1], dp[-2][0])
