[LeetCode]Predict the Winner

递归的做法就是minimax，每次递归我们就两种可能，我们要计算的就是当前player取的所有数的和对手optimal move情况下取的和的差值。如果第一个层对应的值为正就说明可以赢，否则就输。时间复杂度O(2^N)，N为array的长度。代码如下：

	class Solution {
	public:
	bool PredictTheWinner(vector<int>& nums) {
	return minimax(nums, 0, nums.size() - 1) >= 0;
	}
	private:
	int minimax(vector<int>& nums, int lo, int hi)
	{
	if (lo > hi)return 0;
	return max(nums[lo] - minimax(nums, lo + 1, hi), nums[hi] - minimax(nums, lo, hi - 1));
	}
	};

view raw Predict the Winner_1.cpp hosted with ❤ by GitHub

另一个思路就是dp，dp[i][j]代表当前player在还剩从i到j的元素的时候，能比对手多取的值。那么我们有递推公式:

• dp[i][j] = max(array[i] - dp[i + 1][j], array[j] - dp[i][j - 1])

时间空间复杂度均为O(N^2)，代码如下：

	class Solution {
	public:
	bool PredictTheWinner(vector<int>& nums) {
	int n = nums.size();
	vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
	for (int len = 1; len <= n; ++len)
	{
	for (int i = 0; i <= n - len; ++i)
	{
	dp[i][i + len - 1] = len == 1? nums[i]: max(nums[i] - dp[i + 1][i + len - 1], nums[i + len - 1] - dp[i][i + len - 2]);
	}
	}
	return dp[0][n - 1] >= 0;
	}
	};

view raw Predict the Winner_2.cpp hosted with ❤ by GitHub