# 464. Can I Win
Two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.
Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.
You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.
Example:
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.
# Solution
Approach 1: (memoized) recursion.
# Code (Python)
Approach 1:
def canIWin(self, upper_bound: int, total: int) -> bool:
if total == 0:
return True
if (1 + upper_bound) * upper_bound / 2 < total:
return False
if (1 + upper_bound) * upper_bound / 2 == total:
return True if upper_bound % 2 == 1 else 0
#return self._play([i for i in range(1, upper_bound + 1)], total)
return self._play_with_cache(tuple([i for i in range(1, upper_bound + 1)]), total, {})
def _play(self, nums, left):
if nums[-1] >= left:
return True
#OR:
#if left <= 0:
# return False
for i in range(len(nums)):
if not self._play(nums[:i] + nums[i+1:], left - nums[i]):
return True
return False
def _play_with_cache(self, nums, left, cache):
if nums[-1] >= left:
return True
# the key in the cache is a tuple of nums -- no need to record sum left because it depends on what's left in nums
if nums in cache:
return cache[nums]
for i in range(len(nums)):
if not self._play(tuple(nums[:i] + nums[i+1:]), left - nums[i]):
cache[nums] = True
return True
cache[nums] = False
return False
Approach 2:
# Code (C++)
Approach 1:
Approach 2: