头脑风暴：除数博弈
题目
爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字 n 。在每个玩家的回合，玩家需要执行以下操作：
选出任一 x，满足 0 < x < n 且 n % x == 0 。
用 n - x 替换黑板上的数字 n 。
如果玩家无法执行这些操作，就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 true 。假设两个玩家都以最佳状态参与游戏。
示例 1:
复制代码
示例 2:
复制代码
解题思路
dp[i]：表示在 i 的位置，Alice 是否能够取得胜利。
Alice 在 n 的位置能不能胜利，取决于 n - x 的位置 Bob 能不能胜利。
若 n - x 这个位置 Bob 无法胜利，则 Alice 在位置 n 一定是能胜利的，即 dp[n] = true，此时直接结束内层循环即可。因为在当前遍历的 n 值中，Alice 已经能赢了，所以后面的就不需要比较了，直接对 N 中的下一个 n 值进行判断即可。
代码实现
复制代码
最后
时间复杂度：O(n²)
空间复杂度：O(n)
版权声明: 本文为 InfoQ 作者【HelloWorld杰少】的原创文章。
原文链接:【http://xie.infoq.cn/article/99c24feba224a06eabeb9486c】。文章转载请联系作者。
佛系编码 2019.05.13 加入
红鲤鱼与绿鲤鱼与驴。
评论