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.
Example 1:
Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false
Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.
For short notation, let M = maxChoosableInteger and T = desiredTotal.
Key Observation: the state of the game is completely determined by currently available numbers to pick in the common pool.
State of Game: initially, we have all M numbers [1, M] available in the pool. Each number may or may not be picked at a state of the game later on, so we have maximum 2^M different states. Note that M <= 20, so int range is enough to cover it. For memorization, we define int k as the key for a game state, where
the i-th bit of k, i.e., k&(1<<i) represents the availability of number i+1 (1: picked; 0: not picked).
At state k, the current player could pick any unpicked number from the pool, so state k can only go to one of the valid next states k':
if i-th bit of k is 0, set it to be 1, i.e., next state k' = k|(1<<i).
Recursion: apparently
the current player can win at state k iff opponent can't win at some valid next state k'.
class Solution {
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
if (desiredTotal <= maxChoosableInteger) return true;
int sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
if (sum < desiredTotal) return false;
Boolean[] dp = new Boolean[1 << maxChoosableInteger];
return helper(0, dp, maxChoosableInteger, desiredTotal);
}
private boolean helper(int mask, Boolean[] dp, int maxChoosableInteger, int desiredTotal) {
if (desiredTotal <= 0) {
// System.out.println(p + ", " + sum + ", " + Integer.toBinaryString(mask));
return false;
}
if (dp[mask] != null) {
return dp[mask];
}
dp[mask] = false;
for (int i = 0; i < maxChoosableInteger; i ++) {
if ((mask & (1 << i)) == 0 && !helper(mask | (1 << i), dp, maxChoosableInteger, desiredTotal - i - 1)) {
dp[mask] = true;
break;
}
}
return dp[mask];
}
}