464. 我能赢吗

 1 class Solution 
 2 {
 3 public:
 4   bool canIWin(int M, int T) 
 5   {
 6       if (M*(M+1)/2 < T) return false;
 7       if (T <= M) return true;
 8       m_ = vector<int>(1 << M, 0);//每一个数可能选，也可能不选，即有2**M种
 9       return canIWin(M, T, 0);
10   }
11 private:
12   vector<int> m_; // 0: unknown, 1: won, -1: lost
13   bool canIWin(int M, int T, int state) //以先手的身份来看
14   {
15       if (T <= 0) return false;//就说明后手已经提前到达了T
16       if (m_[state]) return m_[state] == 1;//如果m_[state]的状态不为0,则一定能分出胜负
17       for (int i = 0; i < M; ++i) //0、1、...、M-1
18       {
19           if (state & (1 << i)) continue; // 判断当前所用数字的状态   
20           // 如果让后手去选择,后手输了,则说明先手一定会赢
21           if (!canIWin(M, T - (i + 1), state | (1 << i)))  return m_[state] = 1;
22       }
23       //如果for循环语句先手的m_[state]的状态并没有置为1,就说明后手赢了，应该置为-1
24       m_[state] = -1;
25       return false;
26   }
27 };