9-1算法，使用动态规划(预测赢家、石子游戏)

预测赢家

题目描述

给定一个表示分数的非负整数数组。玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。

给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1：

输入：[1, 5, 2]
输出：False
解释：一开始，玩家1可以从1和2中进行选择。
如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。
所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。
因此，玩家 1 永远不会成为赢家，返回 False 。

示例 2：

输入：[1, 5, 233, 7]
输出：True
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
     最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 True，表示玩家 1 可以成为赢家。

提示：

1 <= 给定的数组长度 <= 20.
数组里所有分数都为非负数且不会大于 10000000 。
如果最终两个玩家的分数相等，那么玩家 1 仍为赢家。

思路分析

一个能够使用动态规划求解的问题，很关键的一点就是找出其中的重复子问题。

使用nums数组来存储这个分数数组，假定数组中一共有len个数。
使用dp数组来存储玩家1比玩家2高出的分数，那么当我们在分析nums数组的子数组时，很容易知道
当数组的长度为1时，那么先选的玩家（玩家1）一定获胜，所以玩家1比玩家2高出的分数即为dp[i][i] = nums[i],
当数组的长度为2时，那么先选的玩家（玩家1）也一定获胜，因为如果有一种选法可以使得玩家2获胜，那么玩家1就可以做出与之前相反的选择来保证胜利,两个玩家的分数差的绝对值即为
dp[i][i+1] = abs(nums[i] - nums[i+1])。实际上，当数组的长度为偶数时，这个说法都成立。
当数组的长度继续增加时，先选的玩家选择队首或者队尾的某个数以后，后选的玩家能够在接下来的选择中取得最高分的选择就一定是之前数组长度更短时，先选的玩家的选法，所以，此时两个玩家的分数差可以表示为dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])。这就得到了状态转移方程，使用子问题的解决当前问题。

在这里需要注意所有的数组索引都不能超出范围。

所以到最后，我们只需要判断dp[0][len-1] > 0是否成立，就可以知道玩家1能否获胜了。

代码实现

class Solution {

public:
    bool PredictTheWinner(vector<int>& nums) {
		int len = nums.size();
		if(!len%2) return true;
		int dp[len][len];
		for(int i=0; i<len; ++i) {
			dp[i][i] = nums[i];
			if(i < len-1)
				dp[i][i+1] = abs(nums[i] - nums[i+1]);
		}
		for(int L=2; L<len; ++L)
			for(int i=0; i<len; ++i)
				if(L+i < len) {
					dp[i][i+L] = max(nums[i] - dp[i+1][i+L], nums[i+L] - dp[i][i+L-1]);
				}
		return dp[0][len-1] > 0;
	}
};

石子游戏

题目描述

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。

亚历克斯和李轮流进行，亚历克斯先开始。每回合，玩家从行的开始或结束处取走整堆石头。这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。

假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。

示例：

输入：[5,3,4,5]
输出：true
解释：
亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。
如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。
这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。

提示：