leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0464.cpp (757B)

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];