title
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.
Example 2:
Input: maxChoosableInteger = 10, desiredTotal = 0
Output: true
Example 3:
Input: maxChoosableInteger = 10, desiredTotal = 1
Output: true
Constraints:
1 <= maxChoosableInteger <= 200 <= desiredTotal <= 300
给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。
给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/predict-the-winner 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
solution
class Solution:
desiredTotal = 0
maxChoosableInteger = 0
def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
if sum(range(1, maxChoosableInteger+1)) < desiredTotal:
return False
self.memory = {}
self.desiredTotal = desiredTotal
self.maxChoosableInteger = maxChoosableInteger
used = [0 for _ in range(21)]
return self.dfs(used, 0)
memory = {}
# 代表什么位置稳赢，确定选一个数字后，对方肯定会输，这就是稳赢，而不是选所有数字对方都会输。
def dfs(self, used, total) -> bool:
key = (tuple(used), total)
if key in self.memory:
return self.memory.get(key)
res = False
for i in range(1, self.maxChoosableInteger + 1):
if used[i] == 0:
used[i] = 1
if total + i >= self.desiredTotal or not self.dfs(used, total + i):
res = True
used[i] = 0
break
used[i] = 0
self.memory[key] = res
return res