Solution to LeetCode 464 Can I Win.
LeetCode 464
Can I Win (Medium). [link]
Recursion with memorization. Two players are choosing the as best value as they can to win the game - “Game Theory”.
class Solution(object):
def canIWin(self, maxChoosableInteger, desiredTotal):
"""
:type maxChoosableInteger: int
:type desiredTotal: int
:rtype: bool
"""
if maxChoosableInteger >= desiredTotal:
return True # choose max to win
if sum(range(maxChoosableInteger + 1)) < desiredTotal:
return False # not possible to win
def DFS(state, desiredTotal, dp):
if dp[state] != None: # if it exists, return itself
return dp[state]
for i in range(1, maxChoosableInteger + 1):
cur = 1 << (i - 1) # Use binary digit to store status. "cur" means current status
if cur and state != 0: # current value is chosen
continue
if i >= desiredTotal or not DFS(cur | state, desiredTotal - i, dp): # if choose this value can win or the second play cannot win
dp[state] = True
return True
dp[state] = False
return False
return DFS(0, desiredTotal, [None] * (1 << maxChoosableInteger)) # 2 ** maxChoosableInteger
1 << maxChoosableInteger is equivalent to 2 ** maxChoosableInteger. 1 << (i - 1) is equivalent to (i-1) ** 2. cur | state is a syntax to add two binary digits, e.g. 101 | 10 = 111.
