N 次操作后的最大分数和

难度: Hard

给你 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 <= 7
nums.length == 2 * n
1 <= nums[i] <= 10⁶

Submission

运行时间: 756 ms

内存: 16.5 MB

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        nums.sort()
        def gcd(x, y):
            # if x > y:
            #     x, y = y, x
            if y % x == 0:
                return x
            return gcd(y%x, x)
        n = len(nums)
        gcds = [[0]*n for _ in range(n)]
        for x in range(n):
            for y in range(x, n):
                gcds[x][y] = gcd(nums[x], nums[y])

        
        
        dp = [0] * (1<<n)
        for m in range(1<<n):
            if (t:=m.bit_count()) % 2:
                continue
            bits = [i for i, b in enumerate(bin(m)[2:][::-1]) if b=='1']
            for i, x in enumerate(bits):
                for y in bits[i+1:]:
                    cnt = dp[m ^ (1<<x) ^ (1<<y)] + (t>>1) * gcds[x][y]
                    dp[m] = max(cnt, dp[m])

        return dp[-1]

Explain

该题解采用了动态规划与预处理的最大公约数（GCD）的方法。首先，数组被排序，然后计算并存储任意两个元素之间的GCD到一个二维数组中，以减少后续计算中的重复工作。接着，定义一个dp数组，其索引代表一个二进制数，二进制数的每一位表示数组中对应位置的元素是否已经被选择（1代表选择，0代表未选择）。dp数组中的值存储到目前为止可获得的最大分数。对于dp数组的每个状态，如果选取的元素个数是偶数（即可以完全成对），则尝试所有可能的配对方式，计算可能的分数并更新dp状态。最后，dp数组的最后一项（所有元素都被选择时的状态）就是最大分数。

时间复杂度: O(2^(2n) * n^2)

空间复杂度: O((2n)^2 + 2^(2n))

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        nums.sort()
        def gcd(x, y):
            if y % x == 0:
                return x
            return gcd(y%x, x)
        n = len(nums)
        gcds = [[0]*n for _ in range(n)]
        for x in range(n):
            for y in range(x, n):
                gcds[x][y] = gcd(nums[x], nums[y])
        dp = [0] * (1<<n)
        for m in range(1<<n):
            if (t:=m.bit_count()) % 2:
                continue
            bits = [i for i, b in enumerate(bin(m)[2:][::-1]) if b=='1']
            for i, x in enumerate(bits):
                for y in bits[i+1:]:
                    cnt = dp[m ^ (1<<x) ^ (1<<y)] + (t>>1) * gcds[x][y]
                    dp[m] = max(cnt, dp[m])
        return dp[-1]

Explore

在初始化`gcds`数组时，外层循环遍历数组`nums`的所有元素，内层循环从外层循环的当前元素开始至数组末尾。这种方式确保了每一对元素（x, y），其中x <= y，都被考虑到了。由于`gcd(x, y)`与`gcd(y, x)`的结果相同，这种方法避免了重复计算，并且保证了所有可能的元素对都被计算了一次。

使用二进制数来表示元素的选取状态是一种高效的方法，可以直接通过位操作来快速检查、更新和枚举子集。在这种表示方法中，如果一个二进制数的第i位是1，则表示数组中的第i个元素被选取了；如果是0，则表示未被选取。这使得动态规划的状态转移和子状态的检索变得更加直接和高效。

在更新`dp[m]`时，`cnt`的计算考虑了从状态m移除两个已选元素x和y的子状态`dp[m ^ (1<<x) ^ (1<<y)]`，即未选择x和y之前的状态。然后，基于该子状态的分数，加上当前步骤的分数`(t>>1) * gcds[x][y]`。这样做确保了每次更新是在正确的基础上增加新的分数，因为它建立在之前已经计算好的最优子问题解的基础上。

`t`是当前状态m中选取的元素个数的二进制表示中1的个数。`t>>1`是`t`右移一位的结果，即`t`除以2的整数结果，这代表了已经进行的配对次数（因为每次配对需要两个元素）。每次配对的分数是当前配对次数乘以这对元素的最大公约数。这里的操作次数`i`实际上是通过`t>>1`来计算的，`i`表示第i次配对，从1开始计数。