最近刷题遇到几道dp给我干碎了，于是决定坚持刷两周的dp题，每道题都写好题解方便以后复习

---

题目

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：

选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 False。假设两个玩家都以最佳状态参与游戏。

1 <= N <= 1000

---

分析

本题可以从1开始递推，数字为1时，A必败，记1为必败数，再往后的每个数字，寻找是否存在j，使得这个数字减去j以后得到的数字是一个必败数，如果是，则A可以必胜，否则A必败。（如果找不到某个j使得i-j是一个必败数，那么i减去任何一个数都是一个必胜数，那么B就必胜了）

---

代码

 1 class Solution {
 2 public:
 3     int dp[1001];
 4     bool divisorGame(int N) {
 5         dp[1]=0;
 6         for(int i=2;i<=N;i++)
 7         {
 8             for(int j=1;j<i;j++)
 9             {
10                 if(i%j==0&&dp[i-j]==0)
11                 {
12                     dp[i]=1;
13                     break;
14                 }
15             }
16         }
17         if(dp[N]==1)
18         {
19             return true;
20         }
21         else
22         {
23             return false;
24         }
25     }
26 };