leetcode

0 class Solution {

1 static int8_t dp[1 << 20];

2

3 int rec(int maxi, int tgt, int k) {

4 if (dp[k] != 0) return dp[k] > 0;

5 if (tgt <= 0) return false;

6

7 for (int i = 1, mask = 1; i <= maxi; mask <<= 1, i++) {

8 if (k & mask) continue;

9 if (rec(maxi, tgt - i, k | mask)) continue;

10 dp[k] = 1;

11 return true;

12 }

13

14 dp[k] = -1;

15 return false;

16 }

17

18 public:

19 bool canIWin(int maxi, int tgt) {

20 if (tgt <= maxi) return true;

21

22 const int sum = maxi * (maxi + 1) / 2;

23 if (sum < tgt) return false;

24 if (sum == tgt) return maxi % 2;

25

26 memset(dp, 0x00, sizeof(dp));

27 return rec(maxi, tgt, 0);

28 }

29 };

30

31 int8_t Solution::dp[1 << 20];