中等

问题描述

在 "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

深度优先搜索（TLE）

这是一道关于博弈论的题目，对于博弈问题，都是认为博弈双方是足够聪明的，每次都会采用最优方案。

最朴素的做法是，穷举所有的可能性，判断其中是否有一种方案是必胜的方案。

首先我们用一个集合记录可选取的数，玩家（不论是自己还是对手）当前局，从可选数集合从选取一个数，如果集合中的某个数加上轮累计和大于等于目标值，说明当前玩家获得胜利，对手失败；如果集合中的数都选取后加上轮累计和都无法大于等于目标值，则轮到对手回合，如此往复，直到存在一种选取方式能够使累计和大于等于目标值或对手必败或可选数用光。

/**
 * @param {number} maxChoosableInteger
 * @param {number} desiredTotal
 * @return {boolean}
 */
var canIWin = function (maxChoosableInteger, desiredTotal) {
  const set = new Set()
  for (let i = 1; i <= maxChoosableInteger; i++) {
    set.add(i)
  }
  const dfs = (choosable, sum) => {
    for (const num of choosable) {
      if (sum + num >= desiredTotal) {
        return true
      } else {
        const cp_set = new Set(Array.from(choosable))
        cp_set.delete(num)
        if (!dfs(cp_set, sum + num)) {
          return true
        }
      }
    }
    return false
  }
  return dfs(set, 0)
}

• 时间复杂度：$O(2^n \times n)$
• 空间复杂度：$O(2^n)$

这个版本代码会 $TLE$，需要继续优化

状态压缩（TLE）

使用 $Set$ 去记录可选数，每层搜索都需要进行一次拷贝，效率比较低。由于可选数最大不超过 $20$，我们可以进行状态压缩，使用一个整数，用整数上的二进制位（为了方便编码，从$0$开始）作为标记，看某个数是否已经使用。

• 如 $state = 0$，它的二进制是 $0$，表示全部数都未使用。
• 如 $state = 6$，它的二进制是 $110$，表示$1$和$2$已经被使用。
• 如 $state = 22$，它的二进制是 $10110$，表示$1$、$2$、$4$都已经被使用。

/**
 * @param {number} maxChoosableInteger
 * @param {number} desiredTotal
 * @return {boolean}
 */
var canIWin = function (maxChoosableInteger, desiredTotal) {
  const dfs = (state, sum) => {
    for (let i = 1; i <= maxChoosableInteger; i++) {
      if (((state >> i) & 1) === 0) {
        if (sum + i >= desiredTotal) {
          return true
        } else {
          if (!dfs(state | (1 << i), sum + i)) {
            return true
          }
        }
      }
    }
    return false
  }
  return dfs(0, 0)
}

• 时间复杂度：$O(2^n \times n)$
• 空间复杂度：$O(2^n)$

虽然省去了$Set$的开销，但依然会 $TEL$，需要继续优化

提前判断 + 记忆化搜索

实际上，有两种情况可以马上判断是否能够能赢：

• 把 $1$ 到 $maxChoosableInteger$ 所有的数字全都累加，依然无法到达 $desiredTotal$，双发都无法赢，那就无法赢了。
• $maxChoosableInteger$ 大于等于$desiredTotal$，先手直接选最大的数就赢了。

其次，对于某个 $state$ ，它已选取的数是已知的，得到的 $sum$ 肯定是固定的。无论是先选 $1$ 再选 $2$，还是先选 $2$ 再选 $1$，所得到的 $state$ 都会等于 $6 (110)$，后面的计算也必然是相等的，我们就可以对计算结果缓存下来，下次遇到相同的 $state$ 就可以直接返回结果了，减少了大量重复计算。

/**
 * @param {number} maxChoosableInteger
 * @param {number} desiredTotal
 * @return {boolean}
 */
var canIWin = function (maxChoosableInteger, desiredTotal) {
  if ((maxChoosableInteger * (maxChoosableInteger + 1)) / 2 < desiredTotal) return false
  if (maxChoosableInteger >= desiredTotal) return true
  const memo = new Array(1 << maxChoosableInteger)
  const dfs = (state, sum) => {
    if (memo[state] != null) return memo[state]
    for (let i = 1; i <= maxChoosableInteger; i++) {
      if (((state >> i) & 1) === 0) {
        if (sum + i >= desiredTotal) {
          memo[state] = true
          return true
        } else {
          if (!dfs(state | (1 << i), sum + i)) {
            memo[state] = true
            return true
          }
        }
      }
    }
    memo[state] = false
    return false
  }
  return dfs(0, 0)
}

• 时间复杂度：$O(2^n \times n)$
• 空间复杂度：$O(2^n)$