前言

題目鏈接

給你一個整數(shù)數(shù)組 nums 。玩家 1 和玩家 2 基于這個數(shù)組設(shè)計了一個游戲。

玩家 1 和玩家 2 輪流進行自己的回合，玩家 1 先手。開始時，兩個玩家的初始分值都是 0 。每一回合，玩家從數(shù)組的任意一端取一個數(shù)字（即，nums[0] 或 nums[nums.length - 1]），取到的數(shù)字將會從數(shù)組中移除（數(shù)組長度減 1 ）。玩家選中的數(shù)字將會加到他的得分上。當數(shù)組中沒有剩余數(shù)字可取時，游戲結(jié)束。

如果玩家 1 能成為贏家，返回 true 。如果兩個玩家得分相等，同樣認為玩家 1 是游戲的贏家，也返回 true 。你可以假設(shè)每個玩家的玩法都會使他的分數(shù)最大化。

一、題意解析

兩個值的時候必然是取較大的，三個值，取一個能使自己分數(shù)和最大的，后手必然留較小的給先手，因
此先手選一個值加上該較小值最大化。

由于"每個玩家的玩法都會使他的分數(shù)最大化"，所以先手后手玩家的策略方式是一樣的，只是先后次序不同而已。

先手選的值，應(yīng)該比后手能選的值，達到"差值最大"的效果;
同理，后手選的值也會盡量比下一次先手選的值，達到"差值最大"的效果;
即:決策代碼是一致的。

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;
}

二、動態(tài)規(guī)劃

喬治·桑塔亞納說過，“那些遺忘過去的人注定要重蹈覆轍?！边@句話放在問題求解過程中也同樣適用。不懂動態(tài)規(guī)劃的人
會在解決過的問題上再次浪費時間，懂的人則會事半功倍。

一種可以用動態(tài)規(guī)劃解決的情況就是會有反復出現(xiàn)的子問題，然后這些子問題還會包含更小的子問題。相比于不斷嘗試去解決這些反復出現(xiàn)的子問題，動態(tài)規(guī)劃會嘗試一次解決更小的子問題。之后我們可以將結(jié)果輸出記錄在表格中，我們在之后的計算中可以把這些記錄作為問題的原始解。

以下是兩種不同的動態(tài)規(guī)劃解決方案：

自上而下：你從最頂端開始不斷地分解問題，直到你看到問題已經(jīng)分解到最小并已得到解決，之后只用返回保存的答案即可。這叫做記憶存儲（Memoization）。

自下而上：你可以直接開始解決較小的子問題，從而獲得最好的解決方案。在此過程中，你需要保證在解決問題之前先解決子問題。這可以稱為表格填充算法（Tabulation，table-filling algorithm）。

動態(tài)規(guī)劃是逐一解決小問題，最終可以得到大問題答案的解決方案。

1)假設(shè)只有1個整數(shù)，先手后手的最大差值就是這個唯一的整數(shù);

2)假設(shè)只有2個整數(shù)，先手后手的最大差值應(yīng)該是:
先手盡量取最大值，后手在剩下的數(shù)中盡量去最大值，然后兩數(shù)相減得到最大差值

3）假設(shè)有3個整數(shù)，先手盡量取一個最大值，后手也會在剩下2個數(shù)中，確保后手盡可能大，
即：后手保證在剩下2個數(shù)中，達到最大差值的效果。因此可以利用2)的方法。

4）假設(shè)有4個整數(shù)，方法同3)。先手盡量取一個最大值，后手在剩下3個數(shù)中，
確保后手盡可能大。因此可以利用3)的方法。

因此，要求數(shù)組中索引 0 到 length 的最大差值，我們需要這么做:

1）想求[0, length]范圍的最大差值, 需求出數(shù)組范圍比[0, length]小1 的最大差值;
2) 想求[0, length]小1 范圍的最大差值, 需求出數(shù)組范圍比[0, length]小2 的最大差值;
3) 想求[0, length]小2 范圍的最大差值, 需求出數(shù)組范圍比[0, length]小3 的最大差值;文章來源地址http://www.zghlxwxcb.cn/news/detail-400554.html

//使用一個dp數(shù)組, 保存 i,j 之間 "先后手的最大差值";因此需要定義 dp[][];
//dp[left][right] = max(nums[left] - dp[left+1][right], num[right] - dp[left][right-1])
//dp數(shù)組的初始值應(yīng)該是 left == right時, dp[left][left] = nums[left]
//dp[0][length]的意義: 整個數(shù)組先手后手的最大差值。
//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;
}

到了這里，關(guān)于算法 預測贏家（動態(tài)規(guī)劃）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！