题目描述
leetcode 困难题
给你 nums ，它是一个大小为 2 * n 的正整数数组。你必须对这个数组执行 n 次操作。
在第 i 次操作时（操作编号从 1 开始），你需要：
选择两个元素 x 和 y 。
获得分数 i * gcd(x, y) 。
将 x 和 y 从 nums 中删除。
请你返回 n 次操作后你能获得的分数和最大为多少。
函数 gcd(x, y) 是 x 和 y 的最大公约数。
示例1：
1
2
3
4
| 输入：nums = [3,4,6,8]
输出：11
解释：最优操作是：
(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11
|
提示1：
1
2
3
| 1 <= n <= 7
nums.length == 2 * n
1 <= nums[i] <= 10^6
|
状态压缩 + 动态规划
由于 $1 <= n <= 7$ ，使用一个整数 $state$ 表示数组中元素被选取状态, 若从右往左第 $i$ 位为 $1$ 表示 $nums[i]$ 已经被选取，初始为 $0$ 未被选取。
定义 $dp[i]$ 表示当 $state$ 为 $i$ 时剩余元素能获取到的最大分数，那么 $dp[0]$ 为答案。简略的状态转移方程如下：
$$
\begin{align}
&dp(i) = max\{dp(i \oplus 2^a \oplus 2 ^b ) + \frac{zeroCount}{2} \times gcd(nums[a],nums[b])\} \\
\end{align}
$$
其中 $a$, $b$ 为 $i$ 状态下未被选取的下标组合，$zeroCount$ 为未被选取的个数，即 $0$ 的个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| class Solution {
public int maxScore(int[] nums) {
int n = nums.length, init = (int)Math.pow(2, n) - 1;
int[][] cacheGcd = new int[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cacheGcd[i][j] = gcd(nums[i], nums[j]);
}
}
int[] dp = new int[init + 1];
for(int i = init; i >= 0; i--){
List<Integer> zeroIndex = getZeroIndex(i, n);
if((zeroIndex.size() & 1) == 1){
continue;
}
int zeroCount = zeroIndex.size();
for(int j = 0; j < zeroCount; j++){
int a = zeroIndex.get(j);
for(int k = j + 1; k < zeroCount; k++){
int b = zeroIndex.get(k);
dp[i] = Math.max(dp[i], dp[i ^ (int)Math.pow(2, a) ^ (int)Math.pow(2, b)] + zeroCount / 2 * cacheGcd[a][b]);
}
}
}
return dp[0];
}
private List<Integer> getZeroIndex(int i, int n){
List<Integer> ret = new ArrayList<>();
int index = 0;
while(i > 0){
if((i & 1) == 0){
ret.add(index);
}
index++;
i >>= 1;
}
while(index < n) ret.add(index++);
return ret;
}
private int gcd(int a, int b){
return b == 0 ? a : gcd(b, a % b);
}
}
|
状态压缩 + 记忆化搜索
类似的记忆化搜索解法如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| class Solution {
int[][] cacheGcd;
int[] dp;
public int maxScore(int[] nums) {
int n = nums.length, init = (int)Math.pow(2, n) - 1;
cacheGcd = new int[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cacheGcd[i][j] = gcd(nums[i], nums[j]);
}
}
dp = new int[init + 1];
return dfs(0, nums);
}
private int dfs(int state, int[] nums){
if(dp[state] > 0){
return dp[state];
}
List<Integer> zeroIndex = getZeroIndex(state, nums.length);
int curStatePoint = 0;
for(int j = 0; j < zeroIndex.size(); j++){
int a = zeroIndex.get(j);
for(int k = j + 1; k < zeroIndex.size(); k++){
int b = zeroIndex.get(k);
curStatePoint = Math.max(curStatePoint, dfs(state ^ (int)Math.pow(2, a) ^ (int)Math.pow(2, b), nums) + zeroIndex.size() / 2 * cacheGcd[a][b]);
}
}
dp[state] = curStatePoint;
return curStatePoint;
}
private List<Integer> getZeroIndex(int i, int n){
List<Integer> ret = new ArrayList<>();
int index = 0;
while(i > 0){
if((i & 1) == 0){
ret.add(index);
}
index++;
i >>= 1;
}
while(index < n) ret.add(index++);
return ret;
}
private int gcd(int a, int b){
return b == 0 ? a : gcd(b, a % b);
}
}
|
也可以：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
return dfs(0, 1, nums);
}
private int dfs(int state, int round, int[] nums){
if(dp[state] > 0){
return dp[state];
}
List<Integer> zeroIndex = getZeroIndex(state, nums.length);
int curStatePoint = 0;
for(int j = 0; j < zeroIndex.size(); j++){
int a = zeroIndex.get(j);
for(int k = j + 1; k < zeroIndex.size(); k++){
int b = zeroIndex.get(k);
curStatePoint = Math.max(curStatePoint, dfs(state ^ (int)Math.pow(2, a) ^ (int)Math.pow(2, b), round + 1, nums) + round * cacheGcd[a][b]);
}
}
dp[state] = curStatePoint;
return curStatePoint;
}
|