描述 

有两个人玩游戏，给定一个最大可取代数maxChoosableInteger，两个人轮流从1~maxChoosableInteger中取一个数，取过的数不可再取，若其中一方取过以后，所有取过的数的和大于等于desiredTotal，那么这个人获胜。现在给maxChoosableInteger和desiredTotal，问先手是否必胜，假定游戏双方均采取最优策略。你可以假定给出的maxChoosableInteger不超过20，desiredTotal不超过300。

样例 

输入： 

maxChoosableInteger = 10 

desiredTotal = 11 

输出： 

false

说明 

无论先手怎么取数，先手都会输掉游戏。先手可以取到1到10中的任何一个。如果先手取1，那么后手可以取2到10中任何一个。后手如果取10，那么就可以赢得游戏。假如先手取其它的数，那么后手仍然能赢得游戏。

思路 

明显的是，这个全排列问题不能用枚举法来做。1~n的前缀后就是1~n-1的和加上n，用记忆化搜索判断胜利情况。要么当前剩下的desiredTotal小于等于0，要么对于剩下的还未取得数，已经搜索过且是必胜的状态。假设这个状态没有搜索过，就进行判断这个状态，直到遇到判断过的状态或desiredTotal小于等于0。

1 #include "stdafx.h" 2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 class Solution { 7 public: 8     vector
         
           dp; 9     vector
          
            used;10     bool boyi(int maxChoosableInteger, int desiredTotal) {11         int sum = (1 + maxChoosableInteger)*maxChoosableInteger / 2;12         if (sum < desiredTotal) {13             return false;14         }15         if (desiredTotal <= maxChoosableInteger) {16             return true;17         }18         dp.resize(1 << maxChoosableInteger);19         fill(dp.begin(),dp.end(),-1);20         used.resize(maxChoosableInteger + 1);21         fill(used.begin(), used.end(), 0);22         return handler(desiredTotal);23     }24     bool handler(int desiredTotal) {25         if (desiredTotal <= 0)26             return false;27         int key = fmt(used);28         if (dp[key] == -1) {29             for (int i = 1; i < used.size(); i++) {30                 if (!used[i]) {31                     used[i] = true;32                     if (!handler(desiredTotal - i)) {33                         dp[key] = -1;34                         used[i] = false;35                         return true;36                     }37                     used[i] = false;38                 }39             }40             dp[key] = 0;41         }42         return dp[key] == 1;43     }44     int fmt(vector
           
             & used) {45 int num = 0;46 for (int i = 1; i < used.size(); i++) {47 num <<= 1;48 if (used[i]) {49 num |= 1;50 }51 }52 return num;53 }54 };55 56 int main()57 {58 int maxChoosableInteger, desiredTotal;59 cin >> maxChoosableInteger >> desiredTotal;60 Solution sol;61 bool result=sol.boyi(maxChoosableInteger, desiredTotal);62 if (result) {63 cout << "true" << endl;64 }65 else {66 cout << "false" << endl;67 }68 return 0;69 }