Alice and Bob take turns playing a game, with Alice starting first. Initially, there are
nstones 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
Trueif 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' that are smaller than n – are needed again and again, so dynamic programming might work here.
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. Then for
i-j is a square number and
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 = *(n+1) # Alice starts dp = 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]
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 = *(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]