leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0464.cpp (757B)

      1 class Solution {
      2     static int8_t dp[1 << 20];
      3 
      4     int rec(int maxi, int tgt, int k) {
      5         if (dp[k] != 0) return dp[k] > 0;
      6         if (tgt <= 0) return false;
      7 
      8         for (int i = 1, mask = 1; i <= maxi; mask <<= 1, i++) {
      9             if (k & mask) continue;
     10             if (rec(maxi, tgt - i, k | mask)) continue;
     11             dp[k] = 1;
     12             return true;
     13         }
     14 
     15         dp[k] = -1;
     16         return false;
     17     }
     18 
     19   public:
     20     bool canIWin(int maxi, int tgt) {
     21         if (tgt <= maxi) return true;
     22 
     23         const int sum = maxi * (maxi + 1) / 2;
     24         if (sum < tgt) return false;
     25         if (sum == tgt) return maxi % 2;
     26 
     27         memset(dp, 0x00, sizeof(dp));
     28         return rec(maxi, tgt, 0);
     29     }
     30 };
     31 
     32 int8_t Solution::dp[1 << 20];