题目描述

给你 nums，它是一个大小为 2 * n 的正整数数组。你必须对这个数组执行 n 次操作。

在第 i 次操作时（操作编号从 1 开始），你需要：

• 选择两个元素 x 和 y。
• 获得分数 i * gcd(x, y)。
• 将 x 和 y 从 nums 中删除。

请你返回 n 次操作后你能获得的分数和最大为多少。

函数 gcd(x, y) 是 x 和 y 的最大公约数。

样例

输入：nums = [1,2]
输出：1
解释：最优操作是：
(1 * gcd(1, 2)) = 1

输入：nums = [3,4,6,8]
输出：11
解释：最优操作是：
(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11

输入：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^6

算法

(状态压缩动态规划) $O(n^2 2^{2n})$

1. 设状态 $f(s)$ 表示选择的状态集合为 $s$ 时的最大分数。
2. 初始时，$f(0) = 0$ 其余为负无穷。
3. 转移时，枚举两个没有出现在当前 $s$ 中的数字下标 $i$ 和 $j$，转移 $f(s + 2^i + 2^j) = \max(f(s + 2^i + 2^j), f(s) + r * gcd(nums(i), nums(j)))$。其中 $r$ 可以通过 $s$ 计算得出。
4. 最终答案为 $f(2^{2n} - 1)$。

时间复杂度

• 状态数为 $O(2^{2n})$，每次转移需要 $O(n^2)$ 的时间，故总时间复杂度为 $O(n^2 2^{2n})$。

空间复杂度

• 需要 $O(2^{2n})$ 的额外空间存储状态。

C++ 代码

class Solution {
public:
    int maxScore(vector<int>& nums) {
        const int n = nums.size();
        vector<vector<int>> gcd(n, vector<int>(n));

        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                gcd[i][j] = __gcd(nums[i], nums[j]);

        vector<int> f(1 << n, INT_MIN);
        f[0] = 0;

        for (int s = 0; s < (1 << n); s++) {
            if (f[s] == INT_MIN) continue;
            int r = 0;
            for (int i = 0; i < n; i++)
                if (s & (1 << i))
                    r++;

            for (int i = 0; i < n; i++) {
                if (s & (1 << i)) continue;

                for (int j = i + 1; j < n; j++) {
                    if (s & (1 << j)) continue;

                    f[s | (1 << i) | (1 << j)] = max(
                        f[s | (1 << i) | (1 << j)],
                        f[s] + (r / 2 + 1) * gcd[i][j]
                    );
                }
            }
        }

        return f[(1 << n) - 1];
    }
};