[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 nn' 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]

Subscribe
Notify of