Sponsored
Sponsored
This approach uses Dynamic Programming to determine if Alice can win given n stones. We can maintain a boolean array dp where dp[i] represents whether Alice can win with i stones. A state is winning if there's any move that leaves the opponent in a losing state.
Time Complexity: O(n*sqrt(n)), Space Complexity: O(n)
1import math
2
3def winnerSquareGame(n):
4 dp = [False] * (n + 1)
5 for i in range(1, n + 1):
6 for k in range(1, int(math.sqrt(i)) + 1):
7 if not dp[i - k * k]:
8 dp[i] = True
9 break
10 return dp[n]We initialize a boolean list dp and iterate through each state, marking it as winning if there exists a move that forces the opponent into a losing position.
This approach involves a recursive solution with memoization to cache previously computed results. If n is already solved, we return the cached result. Otherwise, we recursively check if any move leaves the opponent in a losing position.
Time Complexity: O(n*sqrt(n)), Space Complexity: O(n)
1var This JavaScript recursive solution uses a helper function for checking state results. The memo stores previous outcomes to avoid duplicate work, iterating over possible square removals to identify winning moves.