本文涉及知识点

C++动态规划
数学 博弈论

LeetCdoe1510. 石子游戏 IV

Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。
一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。
如果石子堆里没有石子了，则无法操作的玩家输掉游戏。
给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True ，否则返回 False 。
示例 1：
输入：n = 1
输出：true
解释：Alice 拿走 1 个石子并赢得胜利，因为 Bob 无法进行任何操作。
示例 2：
输入：n = 2
输出：false
解释：Alice 只能拿走 1 个石子，然后 Bob 拿走最后一个石子并赢得胜利（2 -> 1 -> 0）。
示例 3：
输入：n = 4
输出：true
解释：n 已经是一个平方数，Alice 可以一次全拿掉 4 个石子并赢得胜利（4 -> 0）。
示例 4：
输入：n = 7
输出：false
解释：当 Bob 采取最优策略时，Alice 无法赢得比赛。
如果 Alice 一开始拿走 4 个石子， Bob 会拿走 1 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 3 -> 2 -> 1 -> 0）。
如果 Alice 一开始拿走 1 个石子， Bob 会拿走 4 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 6 -> 2 -> 1 -> 0）。
示例 5：
输入：n = 17
输出：false
解释：如果 Bob 采取最优策略，Alice 无法赢得胜利。
提示：
1 <= n <= 10⁵

动态规划

如果当前有i个石子，当前玩家可以选择 j = 1,4,9…,j <= i。
如果任意dp[i-j]为false，则dp[i]为true，否则为false。

动态规划的状态表示

dp[i] 表示当前玩家有i颗石子时，能否赢。空间复杂度：O(n)

动态规划的转移方程

v = {1,4,9…} ,v[i] <=n。
枚举v[j] <= i。
b = true;
b &= dp[i-j];
dp[i] = !b;
单个状态时间复杂度：O( n \sqrt n n ​)，总时间复杂度：O(n n \sqrt n n ​)

动态规划的初始值

dp[0]= false

动态规划的填表顺序

i =1 To n

动态规划的返回值

dp.back

代码

核心代码

class Solution {
		public:
			bool winnerSquareGame(int n) {
				vector<int> dp(n + 1);
				int iMax = 1;
				for (int i = 1; i <= n; i++) {
					if (iMax * iMax <= i) {	iMax++;}
					bool b = true;
					for (int j = 1; j < iMax; j++) {
						b &= dp[i - j*j];
					}
					dp[i] = !b;
				}
				return dp[n];
			}
		};

单元测试

	TEST_METHOD(TestMethod11)
		{
			Solution sln;
			auto res = sln.winnerSquareGame(1);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod12)
		{
			Solution sln;
			auto res = sln.winnerSquareGame(2);
			AssertEx(false, res);
		}
		TEST_METHOD(TestMethod13)
		{
			Solution sln;
			auto res = sln.winnerSquareGame(4);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod14)
		{
			Solution sln;
			auto res = sln.winnerSquareGame(7);
			AssertEx(false, res);
		}
		TEST_METHOD(TestMethod15)
		{
			Solution sln;
			auto res = sln.winnerSquareGame(17);
			AssertEx(false, res);
		}