LeetCode 1025. 除数博弈（动态规划）

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

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

如果玩家无法执行这些操作，就会输掉游戏。

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/divisor-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

0 ms 6 MB

动态规划

win[n] 表示剩余数字是 n 的时候，胜算 true or false class Solution { public: bool divisorGame(int N) { if(N == 1) return false; vector win(N+1,false); win[1] = false; win[2] = true; for(int Ni = 3, x; Ni <= N; ++Ni) { //当前数字 Ni for(x = 1; x < Ni; ++x) { //我可以取小于 Ni 的 x，留给对手的数字是 Ni-x if(Ni%x == 0 && win[Ni-x]==false) //x可以取，且 留给对手的数使其失败 win[Ni] = true;//那我就赢了，哈哈 } } return win[N]; } };

12 ms 6.1 MB

Michael阿明 原创文章 999获赞 3453访问量 53万+ 关注 他的留言板 展开阅读全文
作者：Michael阿明

博弈 leetcode 动态规划 动态