困难

问题描述

给你 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] <= 106

回溯 + 记忆化搜索 + 状态压缩

$n$ 最大为 $7$。意味着可以使用暴力搜索进行解决，先选择一个数，然后枚举另外一个数与其配对的情况，这里可以使用回溯解决，已选取的数字可以使用状态压缩技巧处理，用 $state$ 记录已选取数字的下标，若下标 $i$ 数字被选取，$state$ 的第 $i$ 位置 $1$。对于每个相同的 $state$，它对应的结果必然是相同的，因此可以使用对 $state$ 进行记忆化，减少重复的计算。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxScore = function (nums) {
  const n = nums.length
  const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b))
  const GCD = new Array(n).fill(0).map(() => new Array(n))
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      GCD[i][j] = gcd(nums[i], nums[j])
    }
  }
  const memo = new Map()
  const backtrack = (cnt, state) => {
    if (memo.has(state)) return memo.get(state)
    if (state === 2 << (n - 1)) return 0
    let max = 0
    for (let i = 0; i < n; i++) {
      if (((state >> i) & 1) === 1) continue
      for (let j = i + 1; j < n; j++) {
        if (((state >> j) & 1) === 1) continue
        const nextState = state | (1 << i) | (1 << j)
        const res = cnt * GCD[i][j] + backtrack(cnt + 1, nextState)
        max = Math.max(res, max)
      }
    }
    memo.set(state, max)
    return max
  }
  return backtrack(1, 0, 0)
}

• 时间复杂度：$O(2^n)$
• 空间复杂度：$O(2^n)$