leetcode

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

0562.cpp (948B)

      1 class Solution {
      2     typedef array<array<int, 16>, 16> cache_t;
      3     static inline constexpr const cache_t cache = []() constexpr -> cache_t {
      4         cache_t cache = {{0}};
      5         for (int i = 1; i <= 15; i++) {
      6             cache[i].fill(INT_MAX);
      7             int count = 0;
      8             for (int j = 1; j <= 15; j++) {
      9                 if (i % j == 0 || j % i == 0) cache[i][count++] = j;
     10             }
     11         }
     12         return cache;
     13     }();
     14 
     15     int dp[16][65536];
     16 
     17   public:
     18     Solution() { memset(dp, 0xFF, sizeof(dp)); }
     19 
     20     int countArrangement(int n, int crnt = 1, uint16_t mask = 0) {
     21         if (crnt > n) return 1;
     22         if (dp[crnt][mask] != -1) return dp[crnt][mask];
     23 
     24         int res = 0;
     25         for (int num : cache[crnt]) {
     26             if (num > n) break;
     27             if (mask & (1 << num)) continue;
     28             res += countArrangement(n, crnt + 1, mask | (1 << num));
     29         }
     30 
     31         return dp[crnt][mask] = res;
     32     }
     33 };