算法 预测赢家（动态规划）

---

前言

题目链接

给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。

玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。

如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。

---

一、题意解析

两个值的时候必然是取较大的，三个值，取一个能使自己分数和最大的，后手必然留较小的给先手，因
此先手选一个值加上该较小值最大化。

由于"每个玩家的玩法都会使他的分数最大化"，所以先手后手玩家的策略方式是一样的，只是先后次序不同而已。

先手选的值，应该比后手能选的值，达到"差值最大"的效果;
同理，后手选的值也会尽量比下一次先手选的值，达到"差值最大"的效果;
即:决策代码是一致的。

int maxscore(int* nums, int left, int right)
{
	if (left == right)
	{
		return nums[left];
	}

	int sleft = nums[left] - maxscore(nums, left + 1, right);
	int sright = nums[right] - maxscore(nums, left, right - 1);

	return sleft >= sright ? sleft : sright;
}

bool PredictTheWinner(int* nums, int numsSize)
{
	return maxscore(nums, 0 ,numsSize - 1) >= 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二、动态规划

乔治·桑塔亚纳说过，“那些遗忘过去的人注定要重蹈覆辙。”这句话放在问题求解过程中也同样适用。不懂动态规划的人
会在解决过的问题上再次浪费时间，懂的人则会事半功倍。

一种可以用动态规划解决的情况就是会有反复出现的子问题，然后这些子问题还会包含更小的子问题。相比于不断尝试去解决这些反复出现的子问题，动态规划会尝试一次解决更小的子问题。之后我们可以将结果输出记录在表格中，我们在之后的计算中可以把这些记录作为问题的原始解。

以下是两种不同的动态规划解决方案：

自上而下：你从最顶端开始不断地分解问题，直到你看到问题已经分解到最小并已得到解决，之后只用返回保存的答案即可。这叫做记忆存储（Memoization）。

自下而上：你可以直接开始解决较小的子问题，从而获得最好的解决方案。在此过程中，你需要保证在解决问题之前先解决子问题。这可以称为表格填充算法（Tabulation，table-filling algorithm）。

动态规划是逐一解决小问题，最终可以得到大问题答案的解决方案。

1)假设只有1个整数，先手后手的最大差值就是这个唯一的整数;

2)假设只有2个整数，先手后手的最大差值应该是:
先手尽量取最大值，后手在剩下的数中尽量去最大值，然后两数相减得到最大差值

3）假设有3个整数，先手尽量取一个最大值，后手也会在剩下2个数中，确保后手尽可能大，
即：后手保证在剩下2个数中，达到最大差值的效果。因此可以利用2)的方法。

4）假设有4个整数，方法同3)。先手尽量取一个最大值，后手在剩下3个数中，
确保后手尽可能大。因此可以利用3)的方法。

因此，要求数组中索引 0 到 length 的最大差值，我们需要这么做:

1）想求[0, length]范围的最大差值, 需求出数组范围比[0, length]小1 的最大差值;
2) 想求[0, length]小1 范围的最大差值, 需求出数组范围比[0, length]小2 的最大差值;
3) 想求[0, length]小2 范围的最大差值, 需求出数组范围比[0, length]小3 的最大差值;

//使用一个dp数组, 保存 i,j 之间 "先后手的最大差值";因此需要定义 dp[][];
//dp[left][right] = max(nums[left] - dp[left+1][right], num[right] - dp[left][right-1])
//dp数组的初始值应该是 left == right时, dp[left][left] = nums[left]
//dp[0][length]的意义: 整个数组先手后手的最大差值。
//dp[0][length] = max(nums[0] - dp[1][right], num[length] - dp[0][length-1])
int max(int a, int b)
{
	return a > b ? a : b;
}

bool PredictTheWinner(int* nums, int numsSize)
{
	int dp[numsSize][numsSize];

	for (int i = 0; i < numsSize; i++)
	{
		dp[i][i] = nums[i];
	}

	for (int left = numsSize - 2; left >= 0; left--)
	{
		for (int right = left + 1; right < numsSize; right++)
		{
			dp[left][right] = max(nums[left] - dp[left+1][right], nums[right] - dp[left][right-1]);
		}
	}

	return dp[0][numsSize - 1] >= 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

---