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 ii位为1说明原数组中的第i ii位未删除
- 否则表示已删除
。状态dp：
1.dp数组含义：
dp[i]表示对于未删除的数字状态为i时，往下进行操作能获得的最大分数
2.递推公式
对于每个状态s，如果该状态中二进制位为1的个数cnt为偶数，那么可以进行交换操作：枚举s中二进制为1 11的位置，假设位置为i和j，则i和j两个位置的元素可以进行交换操作，此时可以获得的分数为cnt/2∗gcd(nums[i],nums[j])，该状态由从状态s中删除位置为i和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 + l o g C ∗ n 2 ) ，n为数组的长度，C为数组中的最大元素，求最大公约数的时间复杂度为O(logC)，一共要求n∗(n−1)对，因此求取公约数总的时间复杂度为O ( l o g C ∗ n 2 )，动态规划需要判断2 n 个状态，每个状态需要使用双重循环寻找为1的位置，所需要的时间复杂度为O ( 2 n ∗ n 2 )
- 空间复杂度：O ( 2 n + n 2 ) ，最大公约数数组和dp数组的空间开销
状态压缩+dfs+记忆化搜索
- 思路：使用记忆化搜索每个可能的状态，并记录至dp数组中，定义dfs(nums,s,cnt) 表示数字的状态为s时，往下进行操作能获得的最大分数，其余参数的含义为：
。s表示表示数组nums中未删除的数字状态【整数】
- 如果s的从右往左的第i位为1说明原数组中的第i ii位已删除【与方法1相反】
- 否则表示未删除
。cnt表示当前进行的是第cnt操作，与该次操作得分相关
那么f(nums,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 + l o g C ∗ n 2 ) ，n为数组的长度，C为数组中的最大元素，求最大公约数的时间复杂度为O(logC)，一共要求n∗(n−1)对，因此求取公约数总的时间复杂度为O ( l o g C ∗ 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; } }
