LeetCode Can I Win 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~n中拿数字，问哪个人拿到的数字之和先大于等于desiredTotal。 边界条件是，如果n大于等于desiredTotal，则A开始拿最大数肯定能赢；另一种情况是，如果n个数之和都小于desiredTotal，则无论怎么拿都不可能超过desiredTotal，A不能获胜。 我们用一个长度为n的字符串表示n个数字被拿的状态，’0’表示没被拿，’1’表示被拿了，当然可以用int和位运算来表示，我这里用string是偷懒了。 再用一个hash[string][bool]表示当n个数字的状态为string时A获胜的情况。那么每次A可以从string中为’0’的位置拿数字，如果此时sum + i >= desiredTotal则A肯定获胜；或者sum + i < desiredTotal但是下一轮B没有获胜，即 !win(sum + i, desiredTotal, visited, result)，A也是获胜的。 代码如下： [cpp] class Solution { private: bool win(int sum, int &desiredTotal, string &visited, unordered_map<string,bool>& result) { if (result.find(visited) != result.end())return result[visited]; for (int i = 1; i < visited.size(); ++i) { if (visited[i] == ‘0’) { visited[i] = ‘1’; if (sum + i >= desiredTotal || !win(sum + i, desiredTotal, visited, result)) { visited[i] = ‘0’; //reset result[visited] = true; return true; } visited[i] = ‘0’; //reset } } result[visited] = false; return false; } public: bool canIWin(int maxChoosableInteger, int desiredTotal) { if (maxChoosableInteger >= desiredTotal)return true; int sum = (1 + maxChoosableInteger)*maxChoosableInteger / 2; if (sum < desiredTotal)return false; string visited(maxChoosableInteger + 1, ‘0’); unordered_map<string, bool> result; return win(0, desiredTotal, visited, result); } }; [/cpp] 本代码提交AC，用时309MS。]]>