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)
1var winnerSquareGame = function(n) {
2 const dp = new Array(n + 1).fill(false);
3 for (let i = 1; i <= n; i++) {
4 for (let k = 1; k * k <= i; k++) {
5 if (!dp[i - k * k]) {
6 dp[i] = true;
7 break;
8 }
9 }
10 }
11 return dp[n];
12};We use an array dp to represent if a state is winning. For each number of stones up to n, we mark it as winning if removing any perfect square results in a losing state for the opponent.
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)
1import
This Java implementation first checks if the state's result is already memoized. It uses a recursive call to determine if removing a square number leads to a losing state for Bob. Memoization stores the results for previously computed states to optimize the solution.