464. 我能赢吗

在 “100 game” 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。
如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？
例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。
给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家是否能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。

示例 1：
输入：maxChoosableInteger = 10, desiredTotal = 11 输出：false 解释： 无论第一个玩家选择哪个整数，他都会失败。 第一个玩家可以选择从 1 到 10 的整数。 如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。 第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利. 同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。
示例 2:
输入：maxChoosableInteger = 10, desiredTotal = 0 输出：true
示例 3:
输入：maxChoosableInteger = 10, desiredTotal = 1 输出：true

提示:

  • 1 <= maxChoosableInteger <= 20
  • 0 <= desiredTotal <= 300

思路：
如何定义状态？考虑当前的局面，轮到哪个玩家，已经选的数字有哪些(可以用二进制数表示状态)
若当前玩家能转移到对手必败态或者直接胜利，当前玩家必胜
否则当前玩家必败

  1. class Solution {
  2.     int n, m;
  3.     int[] f = new int[1 << 21];
  4.     public boolean canIWin(int n, int m) {
  5.         this.n = n;
  6.         this.m = m;
  7.         if (n * (n + 1) / 2 < m) return false;
  9.         Arrays.fill(f, -1);
  10.         return dp(0) == 1 ? true : false; 
  11.     }
  13.     int dp(int st) {
  14.         if (f[st] != -1)
  15.             return f[st];
  17.         int sum = 0;
  18.         for (int i = 1; i <= n; i++ ) {
  19.             if ((st >> i & 1) == 1)
  20.                 sum += i;
  21.         }
  22.         for (int i = 1; i <= n; i++) {
  23.             if ((st >> i & 1) == 1) continue;
  24.             if (sum + i >= m) return (f[st] = 1);
  25.             if (dp(st | (1 << i)) == 0) return (f[st] = 1);
  26.         }
  28.         return f[st] = 0;
  29.     }
  30. }