Last Updated on 2022-01-22 by Clay
題目
Alice and Bob take turns playing a game, with Alice starting first. Initially, there arenstones in a pile. On each player's turn, that player makes a move consisting of removing any non-zero square number of stones in the pile. Also, if a player cannot make a move, he/she loses the game. Given a positive integern, returntrueif and only if Alice wins the game otherwise returnfalse, 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).
Example 3:
Input: n = 4 Output: true Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).
Constraints:
1 <= n <= 105
題目給定數量為 n 的石子（或棋子，圍棋棋子也被稱為 stone），Alice 和 Bob 可以拿走不為 0 的 i 平方的石子，i 可以自己決定。
最好無法拿走石子的情況就算輸掉，由 Alice 先攻，在雙方都做出最佳決策的情況下，如果 Alice 可以獲勝就回傳 true，否則回傳 false。
解題思路
（DP。今天因忙碌暫時跳過紀錄。但這個方法比我一開始想的地回來得好。）
複雜度
| Time Complexity | O(n^1.5)（註記：我不確定該如何估算這題！但我看到此解法他人的估計複雜度為此...... 我會再繼續研究） |
| Space Complexity | O(1) |
C++ 範例程式碼
class Solution {
public:
bool winnerSquareGame(int n) {
vector<bool> dp(n+1);
for (int i=1; i<=n; ++i){
for (int j=1; j*j <= i; ++j){
if(dp[i-j*j] == false) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
};