本文涉及知识点

C++动态规划
数学

LeetCode1406. 石子游戏 III

Alice 和 Bob 继续他们的石子游戏。几堆石子 排成一行 ，每堆石子都对应一个得分，由数组 stoneValue 给出。
Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。
每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。
比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。
假设 Alice 和 Bob 都采取 最优策略 。
如果 Alice 赢了就返回 “Alice” ，Bob 赢了就返回 “Bob”，分数相同返回 “Tie” 。
示例 1：
输入：values = [1,2,3,7]
输出：“Bob”
解释：Alice 总是会输，她的最佳选择是拿走前三堆，得分变成 6 。但是 Bob 的得分为 7，Bob 获胜。
示例 2：
输入：values = [1,2,3,-9]
输出：“Alice”
解释：Alice 要想获胜就必须在第一个回合拿走前三堆石子，给 Bob 留下负分。
如果 Alice 只拿走第一堆，那么她的得分为 1，接下来 Bob 拿走第二、三堆，得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆，输掉比赛。
如果 Alice 拿走前两堆，那么她的得分为 3，接下来 Bob 拿走第三堆，得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆，同样会输掉比赛。
注意，他们都应该采取 最优策略 ，所以在这里 Alice 将选择能够使她获胜的方案。
示例 3：
输入：values = [1,2,3,6]
输出：“Tie”
解释：Alice 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。
提示：
1 <= stoneValue.length <= 5 * 10⁴
-1000 <= stoneValue[i] <= 1000

动态规划的状态表示

dp[i]表示剩余i堆石子时，能获得的最大分数差。空间复杂度：O(n)。

动态规划的转移方程

dp[i] = max(stones[n-i]-dp[i-1],stones[n-i]+stones[n-i+1]-dp[i-2],stones[n-i]+stones[n-i+1]+stones[n-i+2]-dp[i-3])
时间复杂度：O(n)

动态规划的初始值

dp[0]=0

动态规划的填报顺序

i = 1 To n

动态规划的返回值

dp.back()

代码

核心代码

class Solution {
		public:
			string stoneGameIII(vector<int>& stoneValue) {
				const int N = stoneValue.size();
				vector<int> dp(N + 1);
				for (int i = 1; i <= N; i++) {
					dp[i] = stoneValue[N - i]- dp[i - 1];
					if (i >= 2) {
						dp[i] = max(dp[i], stoneValue[N-i] + stoneValue[N-i+1] - dp[i - 2]);
					}
					if (i >= 3) {
						dp[i] = max(dp[i], stoneValue[N - i] + stoneValue[N - i + 1] + stoneValue[N - i + 2] - dp[i - 3]);
					}
				}
				if (0 == dp.back()) {	return "Tie";	}
				return (dp.back() > 0) ? "Alice" : "Bob";
			}
		};

单元测试

	vector<int> stoneValue;
		TEST_METHOD(TestMethod11)
		{
			stoneValue = { 1, 2, 3, 7 };
			auto res = Solution().stoneGameIII(stoneValue);
			AssertEx(string("Bob"), res);
		}
		TEST_METHOD(TestMethod12)
		{
			stoneValue = { 1,2,3,-9 };
			auto res = Solution().stoneGameIII(stoneValue);
			AssertEx(string("Alice"), res);
		}
		TEST_METHOD(TestMethod13)
		{
			stoneValue = { 1,2,3,6 };
			auto res = Solution().stoneGameIII(stoneValue);
			AssertEx(string("Tie"), res);
		}
		TEST_METHOD(TestMethod14)
		{
			stoneValue = { -1,-2,-3 };
			auto res = Solution().stoneGameIII(stoneValue);
			AssertEx(string("Tie"), res);
		}
		TEST_METHOD(TestMethod15)
		{
			stoneValue = { -2 };
			auto res = Solution().stoneGameIII(stoneValue);
			AssertEx(string("Bob"), res);
		}