Maximize Score After N Operations

How it works

Instead of recursion with memoization, we can fill the DP table iteratively. The key observation is that a state with more bits set depends on states with fewer bits set. By iterating from higher masks (more elements used) to lower masks (fewer elements used), we ensure that when we process a state, all states it transitions to are already computed.

The operation number for a given mask is determined by counting how many bits are set and dividing by 2, then adding 1 for the next operation.

Steps

1. Precompute the GCD[i][j] table for all pairs.
2. Create a dp array of size 2^n initialized to 0.
3. Iterate mask from 2^n - 1 down to 0:
   • Count the number of set bits. Skip if it is odd (invalid state).
   • Calculate op = bits / 2 + 1 (the next operation number).
   • For each pair (i, j) not in the current mask:
     • Compute new_mask = mask | (1 << i) | (1 << j).
     • Update dp[mask] = max(dp[mask], op * GCD[i][j] + dp[new_mask]).
4. Return dp[0].

Complexity

• Time complexity: O(n ^ 2 * (2 ^ n + log m))
• Space complexity: O(n ^ 2 + 2 ^ n)

Where n is the size of the array nums and m is the maximum element in the array.

Things to watch for

Forgetting to Multiply by Operation Number

Each operation's score is i * gcd(nums[a], nums[b]) where i is the operation number (1-indexed). Forgetting the multiplier or using 0-indexed operation numbers produces incorrect scores.

Using Wrong Bit Count for Operation Number

In bitmask DP, the operation number is derived from the number of set bits divided by 2, plus 1 (since each operation uses 2 elements). Off-by-one errors in this calculation cascade through all subsequent operations.

Not Precomputing GCD Values

Recomputing gcd(nums[i], nums[j]) inside the DP loop for every state transition leads to TLE on larger inputs. Precomputing all pairwise GCD values into a 2D table provides significant speedup.

Skipping Invalid Bitmask States

In bottom-up DP, states with an odd number of set bits are invalid (you cannot pair up an odd number of elements). Failing to skip these states wastes computation and can cause incorrect transitions.

Incorrect Bitmask Transition

When marking elements as used, the new mask should be mask | (1 << i) | (1 << j). Using XOR or other operations instead of OR can incorrectly toggle bits that are already set, corrupting the state.

from typing import List
from math import gcd

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        n = len(nums)
        N = 1 << n
        GCD = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(i + 1, n):
                GCD[i][j] = gcd(nums[i], nums[j])

        dp = [0] * N
        for mask in range(N - 1, -1, -1):
            bits = bin(mask).count('1')
            if bits % 2 == 1:
                continue
            op = bits // 2 + 1

            for i in range(n):
                if mask & (1 << i):
                    continue
                for j in range(i + 1, n):
                    if mask & (1 << j):
                        continue
                    new_mask = mask | (1 << i) | (1 << j)
                    dp[mask] = max(dp[mask], op * GCD[i][j] + dp[new_mask])

        return dp[0]

class Solution {
public:
    int maxScore(vector<int>& nums) {
        int n = nums.size();
        int N = 1 << n;
        vector<vector<int>> GCD(n, vector<int>(n, 0));

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                GCD[i][j] = std::gcd(nums[i], nums[j]);
            }
        }

        vector<int> dp(N, 0);
        for (int mask = N - 1; mask >= 0; mask--) {
            int bits = __builtin_popcount(mask);
            if (bits % 2 == 1) continue;
            int op = bits / 2 + 1;

            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) continue;
                for (int j = i + 1; j < n; j++) {
                    if (mask & (1 << j)) continue;
                    int newMask = mask | (1 << i) | (1 << j);
                    dp[mask] = max(dp[mask], op * GCD[i][j] + dp[newMask]);
                }
            }
        }
        return dp[0];
    }
};