leetcode1799 --- 状态压缩与动态规划

原题我们看这里leetcode1799

本题主要考察状态压缩和动态规划的部分知识，但是在此基础之上，我们先需要搞懂如何求最大公约数，如何求最大公约数的方法我之前有写到，可以看之前的文章，链接如下(链接)

本题的解题思路

我们可以先预先处理数组nums，数组nums并不是很大[2,14]之间，也就是说最多也就$C_{14}^2$种排列组合可能，我们需要把所有的可能都列出来，方便查找，这里我们将所有的可能都存储在cache中，cache[i][j]就代表着nums[i]与nums[j]之间的最大公约数。

int **cache = (int **)malloc(sizeof(int *)*numsSize);
for (int i=0;i<numsSize;i++) {
    cache[i] = (int *)malloc(sizeof(int)*numsSize);
}
for (int i=0;i<numsSize;i++) {
    for (int j=i;j<numsSize;j++) {
        cache[i][j] = gcd(nums[i],nums[j]);
        cache[j][i] = cache[i][j];
    }
}

我们怎么进行状态压缩呢？我们知道我们最多有14个数字，2的14次方也就16384，这个数字完全是可以放在一个int值中保存的，那我们就可以设置一个f，f的长度就是(1 << numsSize)，这样的话就可以保存所有状态对应的最大奖励值。

int *f = (int *)malloc(sizeof(int)*(1 << numsSize));
memset(f,0,sizeof(int)*(1<<numsSize));

二进制数‘0000 0000 0000 00’对应一种状态，0代表nums中对应的这个数字未被选走，1则代表nums中这个数字已经被选走，比如说’0000 0000 0000 11’代表nums[12], nums[13]已经被选走，对于每种状态，被选走的个数一定是偶数，即状态中1的个数一定是偶数（因为不能抽走单独一个），所以f中一些状态是不存在的，这里我们需要判断一下，__builtin_popcount的用法看链接

for (int i=0;i<(1 << numsSize);i++) {
	int cnt = __builtin_popcount(i);

	if (cnt % 2 != 0) continue;
    for (int m=0; m<numsSize; m++) {
        # TODO
    }
}

我们遍历每一个状态，如果这个状态不合法，就直接跳过，如果这个状态合法，我们进行判断，比如’0000 0000 0000 11’,那么她的前身一定是’0000 0000 0000 00‘这个值，$f[3]=max(f[3],f[0]+cnt/2\ast cache[m][n])$ ，其中cnt为状态数中1的个数，m为某一个1的位置，n为另外一个1的位置，如果看’0000 0000 0000 11’这个例子不是很清晰的话，我们可以看另外一个例子’0000 0000 0011 11’，在这个例子中$f{[}^{\prime }00000000001111^{\prime }]$会有六种可能分别是
$$\{\begin{array}{l}max(f{[}^{\prime }00000000001111^{\prime }],f{[}^{\prime }00000000000011^{\prime }]+4/2\ast cache[10][11])\\ max(f{[}^{\prime }00000000001111^{\prime }],f{[}^{\prime }00000000000101^{\prime }]+4/2\ast cache[10][12])\\ max(f{[}^{\prime }00000000001111^{\prime }],f{[}^{\prime }00000000000110^{\prime }]+4/2\ast cache[10][13])\\ max(f{[}^{\prime }00000000001111^{\prime }],f{[}^{\prime }00000000001001^{\prime }]+4/2\ast cache[11][12])\\ max(f{[}^{\prime }00000000001111^{\prime }],f{[}^{\prime }00000000001010^{\prime }]+4/2\ast cache[11][13])\\ max(f{[}^{\prime }00000000001111^{\prime }],f{[}^{\prime }00000000001100^{\prime }]+4/2\ast cache[12][13])\end{array}$$
列出上面的等式我们可能就明白了，最后我们只需要返回所有都被选走的那个状态，即[(1 << numsSize) - 1]

for (int i=0;i<(1 << numsSize);i++) {
    int cnt = __builtin_popcount(i);

    if (cnt % 2 != 0) continue;

    for (int m=0; m<numsSize; m++) {
        if (i >> m & 1){
            for (int n=m+1; n<numsSize; n++) {
                if (i >> n & 1){
                    f[i] = fmax(f[i],f[i ^ (1 << m) ^ (1 << n)] + cnt / 2 * cache[m][n]);
                }     
            }  
        }
    }
}
return f[(1 << numsSize) - 1];

整体代码

int maxScore(int* nums, int numsSize){
    int **cache = (int **)malloc(sizeof(int *)*numsSize);
    for (int i=0;i<numsSize;i++) {
        cache[i] = (int *)malloc(sizeof(int)*numsSize);
    }
    for (int i=0;i<numsSize;i++) {
        for (int j=i;j<numsSize;j++) {
            cache[i][j] = gcd(nums[i],nums[j]);
            cache[j][i] = cache[i][j];
        }
    }

    int *f = (int *)malloc(sizeof(int)*(1 << numsSize));
    memset(f,0,sizeof(int)*(1<<numsSize));

    for (int i=0;i<(1 << numsSize);i++) {
        int cnt = __builtin_popcount(i);
        
        if (cnt % 2 != 0) continue;
        
        for (int m=0; m<numsSize; m++) {
            if (i >> m & 1){
                for (int n=m+1; n<numsSize; n++) {
                    if (i >> n & 1){
                        f[i] = fmax(f[i],f[i ^ (1 << m) ^ (1 << n)] + cnt / 2 * cache[m][n]);
                    }     
                }  
            }
        }
    }
    return f[(1 << numsSize) - 1];
}

int gcd(int a,int b){
    while(a != b) {
        if (a > b) a -= b;
        else b-= a;
    }
    return a;
}