C++刷leetcode（1025. 除数博弈）【动态规划】

糖逗

题目描述：

1. 爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
   
2. 
   
3. 最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
   
4. 
   
5. 选出任一&#160;x，满足&#160;0 < x < N 且&#160;N % x == 0&#160;。
   
6. 用 N - x&#160;替换黑板上的数字 N 。
   
7. 如果玩家无法执行这些操作，就会输掉游戏。
   
8. 
   
9. 只有在爱丽丝在游戏中取得胜利时才返回&#160;True，否则返回 false。假设两个玩家都以最佳状态参与游戏。
   
10. 
    
11. &#160;
    
12. 
    
13. 示例 1：
    
14. 
    
15. 输入：2
    
16. 输出：true
    
17. 解释：爱丽丝选择 1，鲍勃无法进行操作。
    
18. 示例 2：
    
19. 
    
20. 输入：3
    
21. 输出：false
    
22. 解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
    
23. &#160;
    
24. 
    
25. 提示：
    
26. 
    
27. 1 <= N <= 1000
    
28. 
    
29. 来源：力扣（LeetCode）
    
30. 链接：https://leetcode-cn.com/problems/divisor-game
    
31. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     bool divisorGame(int N) {
   
4.         vector<bool> dp(N+1, 0);
   
5.         dp[0] = false;
   
6.         dp[1] = false;
   
7.         for(int i = 2; i <= N; i++){
   
8.             for(int j = 1; j < i; j++){
   
9.                 if(i % j == 0 && dp[i-j] == false){
   
10.                     dp[i] = true;
    
11.                     break;
    
12.                 }
    
13.                 else continue;
    
14.             }
    
15.         }
    
16.         return dp[N];
    
17.     }
    
18. };

复制代码

参考链接：https://leetcode-cn.com/problems ... ui-hua-by-user2491/