【Leetcode】464. Can I Win

class Solution1(object): def canIWin(self, maxChoosableInteger, desiredTotal): """ DFS表示先手的人能否赢，如果当前不能赢，则选一个数看下一个人能否赢，如果不能，则先手的人能赢。 先手的人遍历所有情况，只要有那么一次先手的人能赢即可。 """ if (1 + maxChoosableInteger)* maxChoosableInteger // 2 < desiredTotal: return False self.memo = {} return self.DFS([i for i in range(1, maxChoosableInteger+1)], desiredTotal) def DFS(self, nums, desiredTotal): hash = str(nums) if hash in self.memo: return self.memo[hash] if desiredTotal <= nums[-1]: return True for i in range(len(nums)): # A选一个数， 然后看B的结果， 如果能有一次成功，那么A就能成功 # A总不能成功，那么return False if self.DFS(nums[:i] + nums[i+1:], desiredTotal - nums[i]) == False: self.memo[hash] = True break self.memo[hash] = False return self.memo[hash] class Solution1(object): """ 回溯法 超时 """ def canIWin(self, maxChoosableInteger, desiredTotal): if (1 + maxChoosableInteger) * maxChoosableInteger // 2 < desiredTotal: return False self.dictionary = {} for i in range(1, maxChoosableInteger+1): self.dictionary[i] = False self.dict = {} return self.DFS(desiredTotal) def DFS(self, desiredTotal): print(desiredTotal) for key in self.dictionary: if not self.dictionary[key]: self.dictionary[key] = True if key >= desiredTotal: # 这里记得修改， self.dictionary[key] = False return True if not self.DFS(desiredTotal-key): self.dictionary[key] = False return True #注意这里 self.dictionary[key] = False return False