1025.除数博弈

链接：1025.除数博弈
难度：Easy
标签：脑筋急转弯、数学、动态规划、博弈
简介：爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

题解 1 - typescript

• 编辑时间：2020-07-24
• 执行用时：76ms
• 内存消耗：37.4MB
• 编程语言：typescript
• 解法介绍：枚举后推断是否能取余 2。

function divisorGame(N: number): boolean {
  return !(N & 1);
}

题解 2 - typescript

• 编辑时间：2020-07-24
• 执行用时：88ms
• 内存消耗：40MB
• 编程语言：typescript
• 解法介绍：动态规划,dp[i]=i 数时是否能赢，dp[i]=可余数中是否有数可匹配。

function divisorGame(N: number): boolean {
  const dp = new Array(N).fill(false);
  for (let i = 2; i <= N; i++) dp[i - 1] = getMods(i).some(num => !dp[i - num - 1]);
  return dp[N - 1];
  function getMods(num: number) {
    const arr = [1];
    for (let i = 2; i < num; i++) {
      if (num % i === 0) arr.push(i);
    }
    return arr;
  }
}