C++刷LeetCode（1510. 石子游戏 IV）【动态规划】【博弈】

糖逗

题目描述：

1. Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。
   
2. 
   
3. 一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。
   
4. 
   
5. 如果石子堆里没有石子了，则无法操作的玩家输掉游戏。
   
6. 
   
7. 给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True ，否则返回 False 。
   
8. 
   
9.  
   
10. 
    
11. 示例 1：
    
12. 
    
13. 输入：n = 1
    
14. 输出：true
    
15. 解释：Alice 拿走 1 个石子并赢得胜利，因为 Bob 无法进行任何操作。
    
16. 示例 2：
    
17. 
    
18. 输入：n = 2
    
19. 输出：false
    
20. 解释：Alice 只能拿走 1 个石子，然后 Bob 拿走最后一个石子并赢得胜利（2 -> 1 -> 0）。
    
21. 示例 3：
    
22. 
    
23. 输入：n = 4
    
24. 输出：true
    
25. 解释：n 已经是一个平方数，Alice 可以一次全拿掉 4 个石子并赢得胜利（4 -> 0）。
    
26. 示例 4：
    
27. 
    
28. 输入：n = 7
    
29. 输出：false
    
30. 解释：当 Bob 采取最优策略时，Alice 无法赢得比赛。
    
31. 如果 Alice 一开始拿走 4 个石子， Bob 会拿走 1 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 3 -> 2 -> 1 -> 0）。
    
32. 如果 Alice 一开始拿走 1 个石子， Bob 会拿走 4 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 6 -> 2 -> 1 -> 0）。
    
33. 示例 5：
    
34. 
    
35. 输入：n = 17
    
36. 输出：false
    
37. 解释：如果 Bob 采取最优策略，Alice 无法赢得胜利。
    
38.  
    
39. 
    
40. 提示：
    
41. 
    
42. 1 <= n <= 10^5
    
43. 
    
44. 来源：力扣（LeetCode）
    
45. 链接：https://leetcode-cn.com/problems/stone-game-iv
    
46. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     bool winnerSquareGame(int n) {
   
4.         vector<bool>dp(n+1, false);
   
5.         for(int i = 1; i <= n; i++){
   
6.             for(int j = 1; j*j <= i; j++){
   
7.                 if(dp[i-j*j] == false){
   
8.                     dp[i] = true;
   
9.                     break;
   
10.                 }
    
11.             }
    
12.         }
    
13.         return dp[n];
    
14.     }
    
15. };

复制代码

参考链接：https://leetcode-cn.com/problems ... -lie-zhi-si-e-qkwa/