[464] Can I Win (TBD)

真是沒法懂 TBD解千愁

int mem[1<<20];

bool dfs(int M, int T, int check) {

if (mem[check]!=0)

return mem[check]>0;

if (T<=0)

return false;

for (int i=1; i<M; i++)

{

if(!(check & (1<<i)) && !dfs(M, T-i-1, check|(1<<i)))

{

mem[check]=1;

return true;

}

}

mem[check]=-1;

return false;

}

bool canIWin(int maxChoosableInteger, int desiredTotal) {

int M = maxChoosableInteger;

int T = desiredTotal;

int sum = (1+M)*M/2;

if (sum < T)

return false;

if (T <2)

return true;

if (sum == T)

return (M%2);

return dfs(M,T,0);

}