原题链接
两个人依次从1~maxNum中选取数字（不可重复选取同一个），累和。当一方选取数字累和后结果大于等于给定的目标数字，则此人胜利。 题目给一个maxNum和targetNum，要求判断先手能否胜利。
思路： 首先判断两种特殊条件：
可选最大值大于等于目标值，直接返回true。其中一个人可选的最大值小于目标值，直接返回false。具体再看题目，题目给出maxNum不大于20，则可状态压缩为一个int（32位）来保存每个数字是否被使用过（题解中利用1-32位进行存储）。 利用一个map存储选取每一个数字的情况，每一次选择前进行判断，如若已经有过选取该数字的情况，则返回map里的值。 遍历i从1到maxN，考虑选取i的情况： 判断先手胜利条件：
选上i数字后，大于等于目标值可胜利。( i >= targetN )选上i数字后，后手输了。( helper(maxN, targetN - i, mask | visited) == false) ) 返回true。 其他情况下，则表示先手输，返回false。Runtime: 137 ms, faster than 43.48% of Java
class Solution { public Map<Integer, Boolean> m = new HashMap<Integer, Boolean>(); public boolean helper(int maxN, int targetN, int visited) { if (m.containsKey(visited)) return m.get(visited); for (int i = 1; i <= maxN; i++) { int mask = (1 << i); if ((mask & visited) == 0 && (i >= targetN || helper(maxN, targetN - i, mask | visited) == false)) { m.put(visited, true); return true; } } m.put(visited, false); return false; } public boolean canIWin(int maxChoosableInteger, int desiredTotal) { if (maxChoosableInteger >= desiredTotal) return true; if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false; return helper(maxChoosableInteger, desiredTotal, 0); } }转载于:https://www.cnblogs.com/ruoh3kou/p/9942431.html
相关资源：数据结构—成绩单生成器