Maximize Score After N Operations LeetCode solution in C++

1
int dp[16384];
2
int gcd_table[14][14];
3

4
class Solution {
5
 public:
6
  int maxScore(vector<int> &nums) {
7
    memset(dp, -1, sizeof(dp));
8
    int sz = nums.size();
9

10
    // Build the GCD table
11
    for (int i = 0; i < sz; ++i) {
12
      for (int j = i + 1; j < sz; ++j) {
13
        gcd_table[i][j] = gcd(nums[i], nums[j]);
14
      }
15
    }
16

17
    // Looping from state 0 to (1<<sz)-1
18
    dp[0] = 0;
19
    for (int s = 0; s < (1 << sz); ++s) {
20
      int cnt = __builtin_popcount(s);
21
      if (cnt & 1) continue; // bitcount can't be odd
22
      for (int i = 0; i < sz; ++i) {
23
        if (s & (1 << i)) continue;
24
        for (int j = i + 1; j < sz; ++j) {
25
          if (s & (1 << j)) continue;
26
          int next_state = s ^ (1 << i) ^ (1 << j);
27
          dp[next_state] = max(dp[next_state], dp[s] + (cnt / 2 + 1) * gcd_table[i][j]);
28
        }
29
      }
30
    }
31
    return dp[(1 << sz) - 1];
32
  }
33
};