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)
1#include <vector>
2#include <cmath>
3using namespace std;
4
5bool winnerSquareGame(int n) {
6 vector<bool> dp(n + 1, false);
7 for (int i = 1; i <= n; ++i) {
8 for (int k = 1; k * k <= i; ++k) {
9 if (!dp[i - k * k]) {
10 dp[i] = true;
11 break;
12 }
13 }
14 }
15 return dp[n];
16}Similar to the C approach, we use a vector to store boolean values. We iterate through possible states, setting each as winning if removing a square number results in a losing position for Bob.
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)
1#include
We use a helper function to recursively determine if a current state is winning while memoizing results for efficiency. The memo array is initialized with -1. For each recursive call, the function checks if removing any square results in a losing state for the opponent.