1510. Perfect Stone Game

Stone Game IV

这次的动态规划题 和往常的DP题稍微有点不一样

多少需要用到一些数学概念 不是完全0数学

奇数VS.偶数

从题目叙述 我们能注意到 只要当前上场的玩家

拿走一把共计 某非零完全平方数 的石头

使得台面上没剩下任何石头 这个玩家就赢了

因为Alice又是老样子 照惯例先攻

于是若初始的石头总数能写成 奇数个非零完全平方数的和

那么Alice就能赢 反之她必输无疑

状态转移方程

从上面的观察 我们已经注意到

对于任何一个迭代到的剩馀石子数量$i$

我们仅需要问：此$i$可否拆成奇数个非零完全平方数的和

而问题的解答 写成状态转移方程便是 对于$1 \leq i$的$i \in N$：

$$squares\_counts[i] = \begin{cases} 1, & \text{if i is a perfect square itself} \\ 1, & \text{if } \exists \, perfect\_square \in [1, i) \text{ s.t. } squares\_counts[i - perfect\_square] = 0 \\ 0, & \text{otherwise} \end{cases}$$

大括号中 第一和第三行非常显而易见 关键在

第二行的理念：$squares\_counts[i - perfect\_square] = 0$

说明$i - perfect\_square$颗石子 只能写成偶数个非零完全平方数的和

而再加上抽走$perfect\_square$颗石子的这步操作

使得$i$颗石子只能写成奇数个非零完全平方数的和 Alice必胜条件

于是我们拿到能写代码的状态转移方程啰👌

C++

#include <vector>
using namespace std;

bool judgeWinnability(int stonesCount) {
    vector<int> squaresCounts(stonesCount + 1, 0);

    for (int num = 1; num <= stonesCount; num++) {
        int maxSqrt = static_cast<int>(pow(num, 0.5));

        if (pow(maxSqrt, 2) == num) {
            squaresCounts[num] += 1; // From 0 to 1.
            continue;
        }

        for (int sqrt = maxSqrt; sqrt >= 1; sqrt--) {
            int residual = num - pow(sqrt, 2);
            if (squaresCounts[residual] == 0) {
                squaresCounts[num] += 1; // From 0 to 1.
                break;
            }
        }
    }

    return squaresCounts.back() == 1;
}

Python

def judge_winnability(stones_count: int) -> bool:
    squares_counts = [0] * (stones_count + 1)

    for num in range(1, stones_count + 1):
        max_sqrt = int(num**0.5)
        if max_sqrt**2 == num:
            squares_counts[num] += 1  # From 0 to 1.
            continue

        for sqrt in range(max_sqrt, 0, -1):
            residual = num - (sqrt**2)
            if squares_counts[residual] == 0:
                squares_counts[num] += 1  # From 0 to 1.
                break

    return squares_counts[-1] == 1

时间复杂度比较微妙 是$O(n\sqrt{n})$ 其中$n$是初始石子数量

每次迭代到的石子数量$i$ 都要检查所有$\leq i$的非零完全平方数

空间复杂度就比较简单 是$O(n)$