专栏 | 九章算法
网址 | http://www.jiuzhang.com
1 题目描述
有两个人玩一个游戏，给定一个最大可取整数 maxChoosableInteger，两个人轮流从1~maxChoosableInteger 中取一个数，取过的数不可再取，若其中一方取过以后，
所有取过的数加起来的和大于等于desiredTotal，那么这个人获胜。
现在给你maxChoosableInteger和desiredTotal，问先手是否必胜，假定游戏双方均采取最优策略。
你可以假定给出的 maxChoosableInteger不超过20,desiredTotal不超过300。
样例
输入 :
maxChoosableInteger = 10 desiredTotal = 11
输出 :
false
样例说明
无论先手怎么取数，先手都会输掉游戏。
先手可以取1到10中的任何一个。如果先手取1，那么后手可以取2到10中的任何一个。
后手如果取10，那么就可以赢得游戏，因为此时和为1+10=11=desiredTotal。
假如先手取其他的数，那么后手仍然能赢得游戏，只要使和大于等于11即可。
2 解题思路
我们读完题发现这题似乎是一题经典的博弈问题，但是有一个很重要的限制条件————每个数只能取一次。
有了这个条件，我们很容易就能想到所有的取数方案，最多有 maxChoosableInteger! 种，即 1~maxChoosableInteger 的全排列。
但是一一枚举这maxChoosableInteger!种方案明显超过了能承受的时间复杂度。
经过对这maxChoosableInteger!种方案的思考，我们可以发现，
虽然方案有阶乘的数量级，但是这么多方案有很多的部分重复计算了，
类似前缀和的思想，我们计算1~n的前缀和，只要计算出1~n-1的前缀和再加上n即可，避免了多余的计算。
这里我们同样可以把之前计算的结果保留下来以方便之后的计算，我们称之为 记忆化搜索 ，和前缀和不同的是，这里用的是自顶向下(类似于分治的把大问题拆分为小问题的求解方法)的求解方法。
在记忆化搜索中，使用了两个条件判断胜利，
一是当前剩下的desiredTotal(减去了取走的数)小于等于0，
二是对于剩下的还未取的数，已经搜索过且是必胜的状态，
假如这个状态没有搜索过，就进行dfs判断这个状态，直到遇到判断过的状态或desiredTotal小于等于0。
其实本题也可以用自下而上的动态规划实现，状态表示和记忆化搜索相同。
对于记录状态的数组，
我们使用01向量表示，0代表这个数没有使用过，1代表已经使用过。
把1~maxChoosableInteger的使用情况定义为一个只有0,1的向量，
比如maxChoosableInteger=3，他们的使用情况有8种，分别是000(没有元素被使用),001,010,100,011,110,101,111(所有元素都被使用)。
再把这个向量转化成十进制数作为下标。
设maxChoosableInteger为n，
除了特殊情况外我们需要计算所有的状态，且每个状态只需要计算一次，则时间和空间复杂度均为O(2^n)。
3 参考代码
4 面试官角度
本题运用了记忆化搜索的方法，
能用记忆化搜索解出的能获得hire的评价，
如果能把状态压缩为一个十进制数，则能获得strong hire的评价。
5 Lintcode相关题目
不同的二叉查找树 http://www.lintcode.com/zh-cn/problem/unique-binary-search-trees/
交叉字符串 http://www.lintcode.com/zh-cn/problem/interleaving-string/
6 九章参考答案
http://www.jiuzhang.com/solution/can-i-win/