title
给你 nums ，它是一个大小为 2 * n 的正整数数组。你必须对这个数组执行 n 次操作。
在第 i 次操作时（操作编号从 1 开始），你需要：
- 选择两个元素
x和y。 - 获得分数
i * gcd(x, y)。 - 将
x和y从nums中删除。
请你返回 n 次操作后你能获得的分数和最大为多少。
函数 gcd(x, y) 是 x 和 y 的最大公约数。
示例 1：
输入：nums = [1,2]
输出：1
解释：最优操作是：
(1 * gcd(1, 2)) = 1
示例 2：
输入：nums = [3,4,6,8]
输出：11
解释：最优操作是：
(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11
示例 3：
输入：nums = [1,2,3,4,5,6]
输出：14
解释：最优操作是：
(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14
提示：
1 <= n <= 7nums.length == 2 * n1 <= nums[i] <= 106
solution
def gcd(x, y):
return x if not y else gcd(y, x % y)
class Solution:
def maxScore(self, nums: List[int]) -> int:
n = len(nums)
m = {}
for i in range(n):
for j in range(i + 1, n):
m[(i, j)] = gcd(nums[i], nums[j])
dp = [0] * (1 << n)
for mask in range(3, 1 << n):
ones = []
for k in range(n):
if (1 << k) & mask:
ones.append(k)
t = dp[mask]
times = len(ones) // 2
for k1 in range(len(ones)):
for k2 in range(k1 + 1, len(ones)):
t = max(t, dp[mask ^ (1 << ones[k1]) ^ (1 << ones[k2])] + times * m[(ones[k1], ones[k2])])
dp[mask] = t
return dp[(1 << n) - 1]