记忆化递归，状态压缩掩码，求解《464. 我能赢吗》
例题
464. 我能赢吗
在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。
如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？
例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。
给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家是否能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。
答案
递归 · 记忆化 · 掩码
var canIWin = function(maxChoosableInteger, desiredTotal) {
if (maxChoosableInteger >= desiredTotal) return true
if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal) return false
const h = new Uint8Array(1 << (maxChoosableInteger + 1))
const d = (mask, curTotal) => {
if (h[mask] > 0) return h[mask] === 1
for (let i = 1; i <= maxChoosableInteger; i++) {
if ((mask & 1 << i) === 0) {
if (curTotal + i >= desiredTotal) return h[mask] = 1, true
if(d(mask | 1 << i, curTotal + i) === false) return h[mask] = 1, true
}
}
return h[mask] = 2, false
}
return d(0, 0)
};function canIWin(maxChoosableInteger: number, desiredTotal: number): boolean {
if (maxChoosableInteger >= desiredTotal) return true
if ((1 + maxChoosableInteger) * maxChoosableInteger >> 1 < desiredTotal) return false
const h = new Uint8Array(1 << (maxChoosableInteger + 1))
const d = (mask, curTotal) => {
if (h[mask] > 0) return h[mask] === 1
for (let i = 1; i <= maxChoosableInteger; i++) {
if ((mask & 1 << i) === 0) {
if (curTotal + i >= desiredTotal) return h[mask] = 1, true
if (d(mask | 1 << i, curTotal + i) === false) return h[mask] = 1, true
}
}
return h[mask] = 2, false
}
return d(0, 0)
};func canIWin(maxChoosableInteger int, desiredTotal int) bool {
if maxChoosableInteger >= desiredTotal {
return true
}
if (1 + maxChoosableInteger) * maxChoosableInteger >> 1 < desiredTotal {
return false
}
h := make([]int, 1 << (maxChoosableInteger + 1))
var d func(mask int, curTotal int) bool
d = func(mask int, curTotal int) bool {
if h[mask] > 0 {
return h[mask] == 1
}
for i := 1; i <= maxChoosableInteger; i++ {
if mask & (1 << i) == 0 {
if curTotal + i >= desiredTotal {
h[mask] = 1
return true
}
if d(mask | (1 << i), curTotal + i) == false {
h[mask] = 1
return true
}
}
}
h[mask] = 2
return false
}
return d(0, 0)
}class Solution {
private $h = [];
function canIWin($maxChoosableInteger, $desiredTotal) {
if ($maxChoosableInteger >= $desiredTotal) return true;
if ((1 + $maxChoosableInteger) * $maxChoosableInteger >> 1 < $desiredTotal) return false;
return $this->d($maxChoosableInteger, $desiredTotal, 0, 0);
}
function d($maxChoosableInteger, $desiredTotal, $mask, $curTotal) {
if (is_null($this->h[$mask]) === false) return $this->h[$mask];
for ($i = 1; $i <= $maxChoosableInteger; $i++) {
if (($mask & 1 << $i) === 0) {
if ($curTotal + $i >= $desiredTotal) return $this->h[$mask] = true;
if ($this->d($maxChoosableInteger, $desiredTotal, $mask | 1 << $i, $curTotal + $i) === false) return $this->h[$mask] = true;
}
}
return $this->h[$mask] = false;
}
}class Solution:
def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
if maxChoosableInteger >= desiredTotal: return True
if (1 + maxChoosableInteger) * maxChoosableInteger >> 1 < desiredTotal: return False
h = [None] * (1 << (maxChoosableInteger + 1))
def d(mask, curTotal):
if h[mask] != None: return h[mask]
for i in range(1, maxChoosableInteger + 1):
if mask & 1 << i > 0: continue
if curTotal + i >= desiredTotal:
h[mask] = True
return True
if d(mask | 1 << i, curTotal + i) == False:
h[mask] = True
return True
h[mask] = False
return False
return d(0, 0)class Solution {
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
if (maxChoosableInteger >= desiredTotal) return true;
if ((1 + maxChoosableInteger) * maxChoosableInteger >> 1 < desiredTotal) return false;
Boolean[] h = new Boolean[1 << (maxChoosableInteger + 1)];
return d(maxChoosableInteger, desiredTotal, 0, 0, h);
}
public boolean d(int maxChoosableInteger, int desiredTotal, int mask, int curTotal, Boolean[] h) {
if (h[mask] != null) return h[mask];
for (int i = 1; i <= maxChoosableInteger; i++) {
if ((mask & 1 << i) == 0) {
if (curTotal + i >= desiredTotal) return h[mask] = true;
if (d(maxChoosableInteger, desiredTotal, mask | 1 << i, curTotal + i, h) == false) return h[mask] = true;
}
}
return h[mask] = false;
}
}
