解法一：动态规划

作为先手只需要找到一种让下一个行动者必输的策略，就可以保证自己必胜。
比如现在是 N ，如果存在 N 的因子 x ，满足N-x 时先手必输，那么 N 时只要取 x 就可以保证先手必胜。反之，找不到这种方案时， N 时先手必输。

  1. import java.util.LinkedList;
  2. import java.util.List;
  4. class Solution {
  5.     public boolean divisorGame(int N) {
  6.         // dp[i]表示数字为i时先手能否保证赢得比赛
  7.         boolean[] dp = new boolean[N + 1];
  8.         dp[1] = false;
  9.         for (int i = 2; i <= N; ++i) {
  10.             dp[i] = false;
  11.             // 只要找到一种必胜策略即可
  12.             for (int j : getFactors(i)) {
  13.                 // 用i-j替换i可以保证下一个先手必输
  14.                 // 那么说明本次操作方有必胜策略
  15.                 if (!dp[i - j]) {
  16.                     dp[i] = true;
  17.                     break;
  18.                 }
  19.             }
  20.         }
  21.         return dp[N];
  22.     }
  24.     /**
  25.      * 获取n的所有因子, 不包括n本身
  26.      * 
  27.      * @param n
  28.      * @return n的所有因子, 不包括n
  29.      */
  30.     private List<Integer> getFactors(int n) {
  31.         List<Integer> ans = new LinkedList<Integer>();
  32.         ans.add(1);
  33.         for (int i = 2; i <= Math.sqrt(n); ++i) {
  34.             if (n % i == 0) {
  35.                 ans.add(i);
  36.                 if (i * i != n) {
  37.                     ans.add(n / i);
  38.                 }
  39.             }
  40.         }
  41.         return ans;
  42.     }
  43. }

解法二：规律

其实根据解法一的思路，可以找到规律。首先关注以下性质。

  • 1是所有数的因子，必有 N-1 这种方案
  • 奇数的所有因子都是奇数，因此当 N 为奇数时， N-x 均为偶数

dp[1]=false ， dp[2]=true ，以这两个为基础，可以通过数学归纳法推断出：当N为偶数时， dp[N-1]=false ，因此 dp[N]=true ；当N为奇数时， dp[N-x] 恒为 true ，因此 dp[N]=false 。

  1. class Solution {
  2.     public boolean divisorGame(int N) {
  3.         return (N % 2 == 0);
  4.     }
  5. }