leetcode464- Can I Win- medium

In the "100 game," two players take turns adding, to a running total, any integer from 1..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 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.

算法：

1.和前面的取石头游戏很像，仍可以从前面的状态转移方程得到可以借鉴的地方，就是我方赢的方法还是，试探取不同的可行的石子个数，如果任意一次有成功将对方置入必输状态，即可了。不过加入不能取重复的的限制瞬间变难，破解方法是DFS，去遍历每种取的顺序的可能。用一个boolean[]数组记录使用过的数字，遍历每种可能，暴力破解。

2.优化时间复杂度。单纯DFS会TLE，因为递归到底层开销很大，而且有很多相同的子状态被重复计算了。所以我们应该中途记录下某个状态对应的boolean结果，如果遍历到某个状态发现记录过直接返回结果即可。

问题：怎么定义一个状态？一开始以为要1.已用过的数字情况 2. total合在一起才是一个状态，后来发现单独一个1就足够了，因为在一个特定的问题中，maxI总是固定的，那如果你1固定了，maxI - 所有用过的数字就是2了，那2也固定了。所以2是包含在1里的。所以最后只要用一个Map来做memo即可。

问题：怎么表示用过数字的情况呢，这里又是一个优化，并不用boolean[] isUsed来表示，这样map要索引到的话每次要开一个新的boolean[]，空间消耗。本题给了限制可使用数字不会超过20，利用它你可以使用int来取代boolean[]。也就是把integer上的每一位0还是1来当成boolean的结果。如TFFT用1001来表示。标记某一数用过没用过就转为位运算了。isUsed = isUsed ^ (1

细节：

1. 这种DFS改变状态的标记isUsed每次改变一定要成对出现，改过，递归，改回来。本题也是要记住在for循环头尾要改，中途直接return要改（只是本题凑巧用int基本数据类型记录状态，如果是return的话本身就不被保留，可以不用改回去了）。

2. 判断胜利有两个条件，一个是这一步就赢了(可以取的数比界线高)，一个是将来我肯定会赢了(我这几种可取的方法里有一种会让对手陷入必败之地)。不要漏了第一种。

3. 放入memo的是你调用这个函数的时候最开始的isUsed状态，而不是你改动后的，千万小心！

4. 位运算的时候尽量还是用括号括一下保证运算顺序，有几个优先级真的很难记，保险一点。

5. 边界条件有意思，一个是如果一开始可取的数就大于边界了，稳赢；一个是如果你们两个把所有数字都取完了都还没到边界，游戏没意义，你们都输