Open Tcdian opened 3 years ago
/**
* @param {number} N
* @return {boolean}
*/
var divisorGame = function(N) {
const dp = new Array(N + 1).fill(false);
dp[2] = true;
for (let i = 3; i <= N; i++) {
for (let j = 1; j < i; j++) {
if (i % j === 0 && !dp[i - j]) {
dp[i] = true;
}
}
}
return dp[N];
};
function divisorGame(N: number): boolean {
const dp: boolean[] = new Array(N + 1).fill(false);
dp[2] = true;
for (let i = 3; i <= N; i++) {
for (let j = 1; j < i; j++) {
if (i % j === 0 && !dp[i - j]) {
dp[i] = true;
}
}
}
return dp[N];
};
1025. Divisor Game
爱丽丝和鲍勃一起玩游戏,他们轮流行动。爱丽丝先手开局。
最初,黑板上有一个数字
N
。在每个玩家的回合,玩家需要执行以下操作:x
,满足0 < x < N
且N % x == 0
。N - x
替换黑板上的数字N
。如果玩家无法执行这些操作,就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 True,否则返回 false。假设两个玩家都以最佳状态参与游戏。
Example 1
Example 2
Note
1 <= N <= 1000