1799. N 次操作后的最大分数和

Hard

题目描述

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

在第 i 次操作中（1-indexed），你将：

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

返回在执行 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^6

解题思路

这道题要求在 n 次操作中选择数对，使得加权 GCD 之和最大。关键观察是我们需要为每轮操作选择最优的数对组合。

核心思路：

这是一个状态压缩动态规划问题，因为 n ≤ 7，数组长度最多为 14
使用位掩码表示哪些数字已经被使用
对于每个状态，枚举所有可能的数对选择
递归计算每种选择下的最大得分

算法步骤：

预处理所有数对的 GCD 值
使用记忆化搜索，状态为当前使用的数字掩码
对于当前状态，计算还需要进行几次操作
枚举所有可能的未使用数对，递归求解
返回所有选择中的最大值

位运算优化：

使用 __builtin_popcount 快速计算已选择的数字个数
通过位掩码高效表示和更新状态

时间复杂度主要来自状态数量（2^(2n)）和每个状态的转移复杂度。

代码实现

class Solution {
public:
    int maxScore(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> gcd_vals(n, vector<int>(n));
        
        // 预计算所有 GCD 值
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                gcd_vals[i][j] = __gcd(nums[i], nums[j]);
            }
        }
        
        vector<int> memo(1 << n, -1);
        
        function<int(int)> dfs = [&](int mask) -> int {
            if (memo[mask] != -1) return memo[mask];
            
            int used = __builtin_popcount(mask);
            if (used == n) return 0;
            
            int operation = used / 2 + 1;
            int max_score = 0;
            
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) continue;
                for (int j = i + 1; j < n; j++) {
                    if (mask & (1 << j)) continue;
                    
                    int new_mask = mask | (1 << i) | (1 << j);
                    int score = operation * gcd_vals[i][j] + dfs(new_mask);
                    max_score = max(max_score, score);
                }
            }
            
            return memo[mask] = max_score;
        };
        
        return dfs(0);
    }
};

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        from math import gcd
        from functools import lru_cache
        
        n = len(nums)
        
        # 预计算所有 GCD 值
        gcd_vals = {}
        for i in range(n):
            for j in range(i + 1, n):
                gcd_vals[(i, j)] = gcd(nums[i], nums[j])
        
        @lru_cache(None)
        def dfs(mask):
            used = bin(mask).count('1')
            if used == n:
                return 0
            
            operation = used // 2 + 1
            max_score = 0
            
            for i in range(n):
                if mask & (1 << i):
                    continue
                for j in range(i + 1, n):
                    if mask & (1 << j):
                        continue
                    
                    new_mask = mask | (1 << i) | (1 << j)
                    score = operation * gcd_vals[(i, j)] + dfs(new_mask)
                    max_score = max(max_score, score)
            
            return max_score
        
        return dfs(0)

public class Solution {
    public int MaxScore(int[] nums) {
        int n = nums.Length;
        int[,] gcdVals = new int[n, n];
        
        // 预计算所有 GCD 值
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                gcdVals[i, j] = GCD(nums[i], nums[j]);
            }
        }
        
        Dictionary<int, int> memo = new Dictionary<int, int>();
        
        int DFS(int mask) {
            if (memo.ContainsKey(mask)) return memo[mask];
            
            int used = CountBits(mask);
            if (used == n) return 0;
            
            int operation = used / 2 + 1;
            int maxScore = 0;
            
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) continue;
                for (int j = i + 1; j < n; j++) {
                    if ((mask & (1 << j)) != 0) continue;
                    
                    int newMask = mask | (1 << i) | (1 << j);
                    int score = operation * gcdVals[i, j] + DFS(newMask);
                    maxScore = Math.Max(maxScore, score);
                }
            }
            
            memo[mask] = maxScore;
            return maxScore;
        }
        
        return DFS(0);
    }
    
    private int GCD(int a, int b) {
        return b == 0 ? a : GCD(b, a % b);
    }
    
    private int CountBits(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n &= n - 1;
        }
        return count;
    }
}

var maxScore = function(nums) {
    const n = nums.length / 2;
    const memo = new Map();
    
    function gcd(a, b) {
        while (b !== 0) {
            [a, b] = [b, a % b];
        }
        return a;
    }
    
    function dp(mask, operation) {
        if (operation > n) return 0;
        
        if (memo.has(mask)) return memo.get(mask);
        
        let maxScore = 0;
        
        for (let i = 0; i < nums.length; i++) {
            if (mask & (1 << i)) continue;
            for (let j = i + 1; j < nums.length; j++) {
                if (mask & (1 << j)) continue;
                
                const newMask = mask | (1 << i) | (1 << j);
                const score = operation * gcd(nums[i], nums[j]) + dp(newMask, operation + 1);
                maxScore = Math.max(maxScore, score);
            }
        }
        
        memo.set(mask, maxScore);
        return maxScore;
    }
    
    return dp(0, 1);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(2^(2n) × n^2)，其中状态总数为 2^(2n)，每个状态需要枚举 O(n^2) 种数对选择
空间复杂度	O(2^(2n) + n^2)，记忆化数组的空间复杂度和 GCD 预处理数组的空间复杂度

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析