力扣刷题系列 -1025.除数博弈

题干题目分析代码实现

题干

原题链接

输入：2 输出：true 解释：爱丽丝选择 1，鲍勃无法进行操作。

输入：3 输出：false 解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

题目分析

本题既可以用动态规划解决，还可以使用数学推理解决动态规划就是判断N在不同值时，先手是否可以必胜状态方程：dp[i]=dp[i] || !dp[i - j]，j为i的因子,遍历所有因子最后的或运算结果即为当前状态的结果数学推理就是得出N为奇数时，先手必败；偶数时，先手必胜

代码实现

动态规划解法：

class Solution { public boolean divisorGame(int N) { if(N == 1){ return false; } boolean[] dp = new boolean[N + 1]; dp[1] = false; dp[2] = true; for(int i = 3; i <= N; ++i){ for(int j = 1; j < i; ++j){ if(i % j == 0){ dp[i] = dp[i] || !dp[i - j]; } } } return dp[N]; } }

数学解法：

class Solution { public boolean divisorGame(int N) { if(N % 2 == 0){ return true; } return false; } }