我能赢吗

在 “100 game” 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。给定两个整数 maxChoosableIntegerLeetCode 464. 我能赢吗 - 图1#card=math&code=%281%20%3C%3D%20maxChoosableInteger%20%3C%3D%2020%29&id=x8ban) （整数池中可选择的最大数）和 desiredTotalLeetCode 464. 我能赢吗 - 图2#card=math&code=%280%20%3C%3D%20desiredTotal%20%3C%3D%20300%29&id=Baf51)（累计和），若先出手的玩家是否能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。相关标签：位运算, 记忆化搜索, 数学, 动态规划, 状态压缩, 博弈。

Can I Win

In the “100 game” two players take turns adding, to a running total, any integer from 1 to 10. The player who first causes the running total to reach or exceed 100 wins. What if we change the game so that players cannot re-use integers? For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total >= 100. Given two integers maxChoosableInteger and desiredTotal, return true if the first player to move can force a win, otherwise, return false. Assume both players play optimally. Related Topics: Math, Dynamic Programming, Bit Manipulation, Memoization, Game Theory, Bitmask.

  1. Input: maxChoosableInteger = 10, desiredTotal = 11
  2. Output: false
  3. Explanation:
  4. No matter which integer the first player choose, the first player will lose.
  5. The first player can choose an integer from 1 up to 10.
  6. If the first player choose 1, the second player can only choose integers from 2 up to 10.
  7. The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
  8. Same with other integers chosen by the first player, the second player will always win.
  1. Input: maxChoosableInteger = 10, desiredTotal = 0
  2. Output: true
  1. Input: maxChoosableInteger = 10, desiredTotal = 1
  2. Output: true