[Leetcode]1510. Stone Game IV

Alice and Bob take turns playing a game, with Alice starting first.
Initially, there are n stones in a pile.  On each player's turn, that player makes a move consisting of removing any non-zero square numberof stones in the pile.
Also, if a player cannot make a move, he/she loses the game.
Given a positive integer n. Return True if and only if Alice wins the game otherwise return False, assuming both players play optimally.

Example 1:
Input: n = 1 Output: true Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.
Example 2:
Input: n = 2 Output: false Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).
Constraints:
1 <= n <= 10^5

To solve this problem given n, we need to ‘follow’ the game rules and make decisions. It’s not hard to find out that the subproblems for n – n' that are smaller than n – are needed again and again, so dynamic programming might work here.

Dynamic programming

We can initiate an array dp[] such that dp[i] indicates Alice winning/losing when Alice move stones with n equals to i. It’s natural that dp[1]=1. Then for j in [1...i], if i-j is a square number and dp[j]==0: dp[i]=1. Note that dp[j]==0 means Alice will lose when she moves, but it also means Bob will lose since Alice is moving now and the next is Bob.

class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        # 1: Alice wins
        # 0: Alice loses
        dp = [0]*(n+1) # Alice starts
        dp[1] = 1

        for i in range(1,n+1):
            for j in range(1,int(i**0.5)+1):
                if dp[i-j**2] == 0:
                    dp[i] = 1
                    break
        return dp[-1]

Optimisation

If we reverse the previous solution, it could achieve O(n). Similarly, we have dp[] but for each i, we could make dp[j]==1 if dp[i]==0 and j-i is a square number.

class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        dp = [0]*(n+1) # Alice starts
        sq = [i*i for i in range(1, int(n**0.5)+1)]
        for i in range(n+1):
            if dp[i] == 0:
                for j in sq:
                    if i + j <= n:
                        dp[i+j] = 1
                    else:
                        break
        return dp[-1]