题目

题目来源：力扣（LeetCode）

在 “100 game” 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和达到或超过 100 的玩家，即为胜者。

如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？

例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。

给定一个整数 maxChoosableInteger （整数池中可选择的最大数）和另一个整数 desiredTotal（累计和），判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）？

你可以假设 maxChoosableInteger 不会大于 20， desiredTotal 不会大于 300。

示例：

输入：
maxChoosableInteger = 10
desiredTotal = 11

输出：
false

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

思路分析

  1. 两种特殊情况

    • 如果整数池中最大能选择的数字 maxChoosableInteger 大于或等于 累计和desiredTotal，先手选择 maxChoosableInteger 后就能达到 desiredTotal 而稳赢，返回 true 。
    • 如果整数池中能选择的所有数字总和比 累计和desiredTotal 要小，则先手无论如何选择都不能赢，返回false 。

  2. 标记选择状态

    • 用二进制位来标记某个数是否已被选择，比如 01 表示数字 1 已被选择，10 表示数字 2 已被选择，11 表示数字 1 和数字 2 都被选择，100 表示数字 3 已被选择，以此类推，1 << (n - 1) 表示 n 已被选择。
    • n 个数共有 2^n (2的n次方) 种被选择与否的状态(state)，比如 2 个数有四种状态：00、01、10、11，用长度为 2^n (2的n次方) 也就是 1 << n 的 dp数组 来存储这些状态(state) 是否已经出现过，以及这些状态(state) 对应是赢(true) 还是输(false) 。

  3. 递归的 3 个参数

    • 当前所有数字被选择与否的状态：state
    • 当前剩余需要到达的目标：desiredTotal
    • 当前各个状态是否出现过及其输赢情况：dp数组

  4. 每次进入递归时：

    • 先判断下当前状态 state 是否已经出现过了，如果出现过就返回 dp[state]，没有就继续往下计算
    • 遍历能够被选择的所有整数 (从 1 到 maxChoosableInteger) ，当前数 i 对应的状态 curr 为 1 << i ，如果当前数 i 已经被选择，即curr && state != 0，直接进入下一个数的选择，因为一个数只能选择一次。
    • 如果当前数 i 比剩余要达到的目标 desiredTotal 要大，说明选了这个数以后游戏就结束了，先手已赢，说明当前状态 state 可以让先手赢，记忆当前数i，即设置 dp[state] = true ，并返回 true。
    • 如果当前先手选了 i 之后还不能马上赢，但是下一步后手选数字的时候输了，也就是 dfs(total - i, state | curr) 返回了 false，说明先手能赢，设置 dp[state] = true ，并返回 false 。

  5. 最后返回的就是第一层递归的结果： dfs(desiredTotal, 0, {}) ，也就是还没开始选择数字的时候 (state 为 0) ，能不能判断先手一定能赢。

代码

  1. /**
  2.  * @param {number} maxChoosableInteger
  3.  * @param {number} desiredTotal
  4.  * @return {boolean}
  5.  */
  6. var canIWin = function (maxChoosableInteger, desiredTotal) {
  7.   // 最大能选择的数字maxChoosableInteger比期望的累计和desiredTotal要大，先手稳赢，返回 true
  8.   if (maxChoosableInteger >= desiredTotal) return true;
  10.   // 能选择的所有数字总和比期望的累计和desiredTotal要小，一定到达不了desiredTotal，先手稳输，返回 false
  11.   var sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
  12.   if (sum < desiredTotal) return false;
  13.   // 记忆化
  14.   // dp 存储某个数被抽过的状态，以及这些状态对应是赢(true) 还是输(false)
  15.   // var dp = {};
  16.   /**
  17.   * @param {number} total 剩余的数量
  18.   * @param {number} state 使用二进制位表示某个数被抽过的状态
  19.   * @param {Object} dp 存储某个数被抽过的状态，以及这些状态对应是赢(true) 还是输(false)
  20.   */
  21.   function dfs(total, state, dp={}) {
  22.     // 当前状态已经出现过，返回 dp[state]
  23.     if (dp[state] !== undefined) return dp[state];
  24.     // 当前状态没有在 dp 中出现过，继续往下计算
  25.     // 遍历能够被选择的所有整数
  26.     for (var i = 1; i <= maxChoosableInteger; i++) {
  27.       // 当前数i 对应的状态
  28.       var curr = 1 << i;
  29.       // 如果当前数i已经被选择cur & state != 0，直接continue进入下一个数的选择，因为一个数只能选一次
  30.       if (curr & state) continue;
  31.       // 如果当前数i比剩余要达到的目标desiredTotal要大，说明选了这个数以后游戏就结束了，
  32.       // 先手已赢，说明当前状态state可以让先手赢，dp[state] = true，并返回 true
  33.       if (i >= total) return dp[state] = true;
  34.       // 如果当前 先手 选了i之后还不能马上赢，但是下一步 后手 选数字的时候选输了
  35.       // 说明先手能赢，dp[state] = true，并返回ture
  36.       if (!dfs(total - i, state | curr, dp)) return dp[state] = true;
  37.     }
  38.     // 如果遍历完了所有的整数，当前state还没有返回过True，
  39.     // 说明这种状态就不能让先手赢，dp[state] = false，并返回false
  40.     return dp[state] = false;
  41.   }
  42.   // 最后返回第一层递归的结果，也就是还没开始选择数字的时候（state为0时），能不能判断先手一定能赢
  43.   return dfs(desiredTotal, 0, {});
  44. };

力扣上的 DP 问题汇总