1510. Perfect Stone Game

Stone Game IV

This dynamic programming problem is a bit different from conventional DP tasks.

It requires some mathematical concepts.

Odd vs. Even

From the problem description, we observe that:

if current player removes a non-zero perfect square number of stones,

and leaves no stones remaining on the table, current player wins.

Alice, as always, takes the first hand by default,

so if initial number of stones can be expressed as a sum of an odd number of non-zero perfect squares,

Alice definitely win. Otherwise, she loses.

State Transition Equation

Based on observations above, we realize:

for any iterated remaining stone count $i$,

we just ask: can this $i$ be expressed by a sum of an odd number of non-zero perfect squares?

This answer, written as a state transition equation for $1 \leq i$ where $i \in \mathbb{N}$, is:

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

While the brace's 1st and 3rd conditions are quite apparent,

our core logic is the 2nd condition: $\mathit{squares\_counts}[i - \mathit{perfect\_square}] = 0$.

This tells: $i - \mathit{perfect\_square}$ stones can only be expressed as a sum of an even number of non-zero perfect squares.

Added with current operation of removing $\mathit{perfect\_square}$ stones,

$i$ stones is for sure a sum of an odd number of non-zero perfect squares, fulfilling Alice's winning condition.

With this clear insight, we have the state transition for our code 👌

C++

#include <vector>
using namespace std;

bool judgeWinnability(int stonesCount) // LeetCode Q.1510.
{
    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:  # LeetCode Q.1510.
    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

Time complexity is somewhat intriguing at $O(n\sqrt{n})$. $n$ represents initial number of stones.

For each stone state $i$, we must evaluate all non-zero perfect squares $\leq i$.

Space complexity is very straightforward at $O(n)$.