难度

  • 简单
  • 中等
  • 困难

    标签

    动态规划

    题目描述

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

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

选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。

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

示例1：

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

实例2：

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

题解

当前 数的获胜dp[i] 依赖于 dp[i-因数] 是否存在必败的可能

  1. class Solution {
  2.     public boolean divisorGame(int N) {
  3.         if(N == 1) {
  4.             return false;
  5.         }
  6.         if(N == 2) {
  7.             return true;
  8.         }
  9.         boolean[] dp = new boolean[N + 1];
  10.         dp[1] = false;
  11.         dp[2] = true;
  12.         for(int i = 3; i <= N; i++) {
  13.             for(int j = 1; j < i; j++) {
  14.                 if((i % j) == 0 && !dp[i - j]) {
  15.                     dp[i] = true;
  16.                     break;
  17.                 }
  18.             }
  19.         }
  20.         return dp[N];
  22.     }
  23. }