# dp solution in c++ with comments

• I think the key to this problem is to use some bitwise operation to record what numbers have been used during the game to minimize the size of hash table as much as possible.

`````` class Solution {
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
if(desiredTotal == 0) return true;

if((maxChoosableInteger+1) * maxChoosableInteger / 2 < desiredTotal)
return false;

unordered_map<int, bool> dp;

// a bit in record being equal to 1 means a number is available
// for example if record is ..1000, it means number 3 has not been used,
// for convenience we do not use the least significant digit.
int record = 0;
for(int i = 0; i < maxChoosableInteger+1; i++) {
record = (record << 1) + 1;
}
return f(desiredTotal, record, dp);
}

bool f(int dt, int record, unordered_map<int, bool> &dp)
{
if(dp.count(record)) {
return dp[record];
}

// we know maxChoosableInteger wont be larger than 20
for(int i = 20; i > 0; i--) {
int bit = 1 << i;

// if this number has not been used
if(record & bit) {
if(i >= dt) {
dp[i] = true;
return true;
}
// mark number i so it has been used and check whether the opponent
// can win. Notice that due to the annoyance of [] operator
// automatically inserting value into a set in c++, we should not
// use dp[...] = f(..., dp) to avoid changing dp BEFORE the
// function is called.
bool t = f(dt-i, record^bit, dp);
dp[record^bit] = t;
if(t == false) {
return true;
}
}
}
return false;

}

};``````

• what a great solution!!!!
Brilliant thought.

and

``````if(i >= dt) {
//dp[i] = true;
return true;
}
``````

I think this line is useless.

• And since 2^21/4B/1024/1024=8MB, I replace hashmap(636 ms) with vector/array(75 ms);

``````class Solution {
private:
vector<int> *winSet;
bool canIWinAux(int numSet, int total) {
int maxnum = maxNum(numSet);
if (maxnum >= total) return true;
if (winSet->at(numSet) != -1) return winSet->at(numSet);
for (int num = 1; num <= maxnum; num++) {
int mask = 1 << (num-1);
//	skip used number
//	skip if take num as first choice
if (canIWinAux((int)(numSet&(~mask)), total - num)) continue;
//	otherwise this num is the smart choice
winSet->at(numSet) = true;
return true;
}
//	have tried every number in numSet and fail to win
winSet->at(numSet) = false;
return false;
}

//	return the maximum number avaliable in the numSet
int maxNum(int numSet) {
int firstBit = 0;
while (numSet) {
firstBit++;
numSet >>= 1;
}
return firstBit;
}

public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
if (desiredTotal>maxChoosableInteger*(maxChoosableInteger + 1) / 2) return false;
if (desiredTotal <= maxChoosableInteger) return true;
if (desiredTotal % (1 + maxChoosableInteger) == 0 && maxChoosableInteger % 2 == 0) return false;

//	numSet: the k-nd bit stands for number k; 1 is usable, 0 is used, -1 is unknown.
int numSet = (1 << (maxChoosableInteger))-1;
winSet = new vector<int>(1 << maxChoosableInteger, -1);
return canIWinAux(numSet, desiredTotal);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.