题解
y总思路:
-
状态压缩DP:
f[]
有2^n个状态,用0/1表示数组nums中每个数的利用情况 -
集合定义:从状态
f[i]
开始取数字(玩游戏),能获取到的最大分数 -
属性:划分f[i]集合中的最大值
分析
例子:nums = [1, 2, 3, 4, 5, 6]
,初始状态可定义为”111111”,表示每个数都没有被用过,现在分析某一个状态f[i]
的集合是怎样的:
- 假设当前状态为”110110”, 表示已经有两个数被取走了,那么我们先计算出0出现的个数,用
cnt
表示,那么当前的操作步数应该为cnt / 2 + 1
(后续计算gcd(a, b) * 步数会用到)。 - 然后,我们发现状态”110110”的最后一步一定会对应到如下状态: ‘100100’ / ‘110000’ / ‘000110’/ ‘010010’ / ‘010100’ / ‘100010’
- 既然最后一步状态是有限且可确定的,那么在”110110”这个状态的属性最大值就是
max(‘100100’ / '110000' / '000110'/ '010010' / '010100' / '100010')
。 - 这样,我们就得到了状态转移方程
f[i] = max(f[i], f[i - (1 << j) - (1 << k)] + gcd(nums[j], nums[k]) * cnt);
时间复杂度
题目中nums.length
最多为2*7=14, 每次取走两个数一共有C(14,2) = 91
中取法,为O(2^14 * 91) = 1.5×10^6 。
class Solution {
private int[] f;
private int gcd(int a, int b) {
return b != 0 ? gcd(b, a % b) : a;
}
public int maxScore(int[] nums) {
int n = nums.length;
f = new int[1 << n];
for (int i = 3; i < 1 << n; i++) {
int cnt = 0;
// 求状态的二进制位 0 的个数
for (int j = 0; j < n; j++) {
if ((i >> j & 1) == 0) cnt++;
}
cnt = cnt / 2 + 1;
for (int j = 0; j < n; j++) {
if ((i >> j & 1) == 1) { // 在剩下的状态找到第一个'1'
for (int k = j + 1; k < n; k++) {
if ((i >> k & 1) == 1) { // 在剩下的状态找到第二个'1'
// 取这两个1,求“分数”
f[i] = Math.max(f[i], f[i - (1 << j) - (1 << k)]
+ gcd(nums[j], nums[k]) * cnt);
}
}
}
}
}
return f[(1 << n) - 1];
}
}