In this Leetcode Can I Win problem solution 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.
Problem solution in Python.
def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
m, d = maxChoosableInteger, desiredTotal
@lru_cache(None)
def pick(num, left):
for i, n in enumerate(num):
# either i win now or another player lose in next turn
if n>=left or not pick(num[:i] + num[i+1:], left-n):
return True
return False
if m >= d:
return True
if m*(m+1)/2 < d:
return False
return pick(tuple([i for i in range(1, m+1)]), d)
Problem solution in Java.
class Solution {
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
if (desiredTotal <= 0) return true;
if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
int[] dp = new int[1 << maxChoosableInteger];
return dfs(dp, 0, maxChoosableInteger, desiredTotal);
}
public boolean dfs(int[] dp, int chs, int max, int target) {
// targer <= 0 means the prior one wins
if (target <= 0) return false;
if (dp[chs] != 0) return dp[chs] == 1;
boolean win = false;
for (int i = 0; i < max; i++) {
// i + 1 not use
if ((chs & (1 << i)) == 0) {
win = win || !dfs(dp, chs ^ (1 << i), max, target - i - 1);
}
}
dp[chs] = win ? 1 : -1;
return win;
}
}
Problem solution in C++.
class Solution {
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
if (maxChoosableInteger >= desiredTotal) return true;
int sum = ((maxChoosableInteger + 1) * maxChoosableInteger) >> 1;
if (sum < desiredTotal) return false;
mp = vector<int>(1 << maxChoosableInteger, -1);
return canWin(0, maxChoosableInteger, desiredTotal);
}
private:
vector<int> mp;
bool canWin(int used, const int &maxChoosableInteger, int desiredTotal) {
if (mp[used] != -1) return mp[used];
for (int i = maxChoosableInteger, bits = 1 << (maxChoosableInteger - 1); i >= 1; --i, bits >>= 1) {
if ((used & bits) != 0) continue;
if (i >= desiredTotal || !canWin(used | bits, maxChoosableInteger, desiredTotal - i)) {
mp[used] = 1;
return true;
}
}
mp[used] = 0;
return false;
}
};