Maximize Score After N Operations

lcpy gen -n 1799   # by problem number
lcpy gen -s maximize_score_after_n_operations   # by problem name

Input: nums = [1,2]
Output: 1
Explanation: The optimal choice of operations is:
(1 * gcd(1, 2)) = 1

Input: nums = [3,4,6,8]
Output: 11
Explanation: The optimal choice of operations is:
(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11

Input: nums = [1,2,3,4,5,6]
Output: 14
Explanation: The optimal choice of operations is:
(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14

from math import gcd


class Solution:
    # Time: O(2^m * m^2) where m = len(nums) = 2n <= 14
    # Space: O(2^m)
    def max_score(self, nums: list[int]) -> int:
        m = len(nums)
        gcd_table = [[0] * m for _ in range(m)]
        for i in range(m):
            for j in range(i + 1, m):
                gcd_table[i][j] = gcd_table[j][i] = gcd(nums[i], nums[j])

        full = (1 << m) - 1
        dp = [0] * (1 << m)
        for mask in range(full):
            op = mask.bit_count() // 2 + 1
            for i in range(m):
                if mask >> i & 1:
                    continue
                for j in range(i + 1, m):
                    if mask >> j & 1:
                        continue
                    nxt = mask | 1 << i | 1 << j
                    dp[nxt] = max(dp[nxt], dp[mask] + op * gcd_table[i][j])
        return dp[full]