当前位置：首页 > news >正文

【每日一题Day64】LC1799N 次操作后的最大分数和 | 状态压缩dp 状态压缩+dfs+记忆化搜索

news 来源：原创 2024/11/21 1:23:57

N 次操作后的最大分数和【LC1799】

You are given nums, an array of positive integers of size 2 * n. You must perform n operations on this array.

In the ith operation (1-indexed), you will:

Choose two elements, x and y.
Receive a score of i * gcd(x, y).
Remove x and y from nums.

Return the maximum score you can receive after performing n operations.

The function gcd(x, y) is the greatest common divisor of x and y.

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

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

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

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

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

虽然花了大半天但是成就感满满

状态压缩dp

思路：

每个数字有两种状态，删除或者未删除，因此可以使用状态压缩记录未删除的数字情况state，便于使用位运算进行状态的遍历及转移；使用状态压缩dp找到将所以数字删除的最大分数
- 状态压缩：使用一个整数s来表示数组nums中未删除的数字状态
  - 如果s的从右往左的第 $i$ 位为1说明原数组中的第 $i$ 位未删除
  - 否则表示已删除
- 状态dp：
  1. dp数组含义：
    
    $d p [i]$ 表示对于未删除的数字状态为 $i$ 时，往下进行操作能获得的最大分数
  2. 递推公式
    
    对于每个状态s，如果该状态中二进制位为1的个数cnt为偶数，那么可以进行交换操作：枚举s中二进制为 $1$ 的位置，假设位置为 $i$ 和 $j$ ，则 $i$ 和 $j$ 两个位置的元素可以进行交换操作，此时可以获得的分数为 $c n t /2 * g c d (n u m s [i], n u m s [j])$ ，该状态由从状态s中删除位置为 $i$ 和 $j$ 的状态转移得到，最后取最大值
    $\{dp[s\oplus 2^i \oplus 2^j] + \frac{cnt}{2}*gcd(nums[i],nums[j])\}$
  3. 初始化
    
    dp数组的长度为状态的个数，即 $2^n$ ， $n$ 为数组的长度
    
    dp[0] = 0;
  4. 遍历顺序
    
    从小到大枚举所有状态
- 预处理：为了避免重复运算每一对数字的最大公约数，我们可以在「动态规划」前对数组中的每一对数字的最大公约数进行预处理操作，记录在数组gcds中。
实现
- 使用辗转相除法求得最大公约数，预处理得到每两个数的最大公约数，记录在gcd数组中
- 使用位运算判断是否是偶数、获得一个状态中1的个数、判断第 $k$ 位是否为1以及状态转移
```
class Solution {
    public int maxScore(int[] nums) {
        int n = nums.length;
        int[] dp = new int[1 << n];
        int[][] gcds = new int[n][n];
        // 预处理gcd
        for (int i = 0; i < n; i++){
            for (int j = i + 1; j < n; j++){
                gcds[i][j] = getGcd(nums[i], nums[j]);
            }
        }
        // 状态dp
        int ALL = (1 << n) - 1;// 全集
        for (int s = 1; s <= ALL; s++){
            int cnt = count1(s);
            // 1的个数为奇数 不合法
            if ( (cnt & 1) == 1){
                continue;
            }
            // 1的个数为偶数
            for (int i = 0; i < n; i++){
                if ( (s >> i & 1) == 1){
                    for (int j = i + 1; j < n; j++){
                        if ( (s >> j & 1) == 1){
                            dp[s] = Math.max(dp[s],dp[s ^ (1 << i) ^ (1 <<j)] + cnt / 2 * gcds[i][j] );
                        }
                    }
                }
            }
        }
        return dp[ALL];

    }
    public int count1 (int s){
        int cnt = 0;
        for (int i = s; i > 0; i >>= 1){
            cnt += i & 1;
        }
        return cnt;
    }
    public int getGcd (int x, int y){
        return y != 0 ? getGcd(y, x % y) : x;
    }
}
```
- 复杂度
  - 时间复杂度： $O(2^n*n^2+logC*n^2)$ ， $n$ 为数组的长度， $C$ 为数组中的最大元素，求最大公约数的时间复杂度为 $O (l o g C)$ ，一共要求 $n * (n - 1)$ 对，因此求取公约数总的时间复杂度为 $O(logC*n^2)$ ，动态规划需要判断 $2^n$ 个状态，每个状态需要使用双重循环寻找为1的位置，所需要的时间复杂度为 $O(2^n*n^2)$
  - 空间复杂度： $O(2^n+n^2)$ ，最大公约数数组和dp数组的空间开销

状态压缩+dfs+记忆化搜索

思路：使用记忆化搜索每个可能的状态，并记录至dp数组中，定义 $df s (n u m s, s, c n t)$ 表示数字的状态为s时，往下进行操作能获得的最大分数，其余参数的含义为：
- $s$ 表示表示数组nums中未删除的数字状态【整数】
  - 如果s的从右往左的第 $i$ 位为1说明原数组中的第 $i$ 位已删除【与方法1相反】
  - 否则表示未删除
- $c n t$ 表示当前进行的是第 $c n t$ 操作，与该次操作得分相关
那么 $f (n u m s, 0, 1)$ 即为最终结果
实现
- 首先使用辗转相除法求得最大公约数，预处理得到每两个数的最大公约数，记录在gcd数组中
- 然后使用记忆化搜索得到最终结果
```
class Solution {
    int n, m;
    int[] dp;
    int[][] gcds;
    public int maxScore(int[] nums) {
        n = nums.length;
        m = n / 2;
        dp = new int[1 << n];
        gcds = new int[n][n];
        // 预处理gcd
        for (int i = 0; i < n; i++){
            for (int j = i + 1; j < n; j++){
                gcds[i][j] = getGcd(nums[i], nums[j]);
            }
        }
        return dfs(nums, 0, 1);       
    }
    public int dfs(int[] nums, int s, int cnt){
        if (cnt > m) return 0;
        if (dp[s] != 0) return dp[s];
        int ans = 0;
        for (int i = 0; i < n; i++){
            if (((s >> i) & 1) == 1) continue;
            for (int j = i + 1; j < n; j++){
                if (((s >> j) & 1) == 1) continue;
                int next = s | (1 << i) | (1 << j);
                ans = Math.max(ans, cnt * gcds[i][j] + dfs(nums, next, cnt + 1));
            }
        }
        dp[s] = ans;
        return ans;
    }
    public int getGcd(int x, int y){
        return y != 0 ? getGcd(y, x % y) : x;
    }
}
```
- 复杂度
  - 时间复杂度： $O(2^n*n^2+logC*n^2)$ ， $n$ 为数组的长度， $C$ 为数组中的最大元素，求最大公约数的时间复杂度为 $O (l o g C)$ ，一共要求 $n * (n - 1)$ 对，因此求取公约数总的时间复杂度为 $O(logC*n^2)$ ，动态规划需要判断 $2^n$ 个状态，每个状态需要使用双重循环寻找为1的位置，所需要的时间复杂度为 $O(2^n*n^2)$
  - 空间复杂度： $O(2^n+n^2)$ ，最大公约数数组、dp数组的空间开销和递归堆栈的开销

贪心

我defeat的贪心…不甘心

class Solution {
    public int maxScore(int[] nums) {
        int m = nums.length;
        int n = m / 2;
        boolean[] isUsed = new boolean[m];
        Arrays.sort(nums);
        // 计算1个个数 1与其他任何数字的gcd只能为1 因此最后处理1 挑其他数字挑剩下的即可
        int[] gcds = new int[n];
        int idx1 = -1;
        while (nums[idx1 + 1] == 1){
            idx1++;
            gcds[idx1] = 1;
        }
        int i = idx1 + 1;
        while (i < n){
            // 第一个未使用过的数字
            int j = idx1 + 1;
            while(isUsed[j]){
                j++;
            }
            // 找到其最大的gcd
            int cur = 0;
            int index = -1;
            for (int k = j + 1; k < m; k++){
                if (isUsed[k]) continue;
                int gcd = getGcd(nums[j],nums[k]);
                if (gcd > cur){
                    cur = gcd;
                    index = k;
                }
            }
            isUsed[j] = true;
            isUsed[index] = true;
            // 存储gcd
            gcds[i] = cur;
            i++;
        }
        // 计算score
        Arrays.sort(gcds);
        int res = 0;
        for (i = 0; i < n; i++){
            res += (i + 1) * gcds[i];
        }
        return res;

    }
    public int getGcd (int x, int y){
        return y != 0 ? getGcd(y, x % y) : x;
    }
}