Leetcode 1799

2022-12-22 498 words One minute

Contents

Leetcode 1799, couldn’t get the solution

Leetcode 1799

Solution

dp + state compression

We have a total of 2n numbers, and the maximum n is 7, so we can consider using binary bits to enumerate whether a certain number is selected. Starting from the initial state 00…00, when a certain bit is selected, it is marked as 1. From Initial state 0 starts searching, select 2 numbers i, j for pairing each time, set position i, j to 1 after selecting 2 numbers each time. mask^(1«i)^(1«j) , until mask=11..11 is selected after all the numbers are selected, the maximum value is updated. Since the simple dfs will time out, state compression is used to memorize the search. For the current mask state, the order of previous selection does not affect the future The maximum value obtained.

dp[mask] represents the maximum score that can be obtained under the current state mask

dfs + memo

class Solution {
public:
    int n;
    vector<int> dp;
    vector<vector<int>> gcds;
    vector<int> nums;
    int maxScore(vector<int>& _nums) {
        nums = _nums;
        n = nums.size();
        dp.resize(1 << n, -1);
        gcds.resize(n, vector<int>((n)));

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                gcds[i][j] = GCD(nums[i], nums[j]);
            }
        }

        dfs(0, 1);
        return dp[0];
    }

private:
    int GCD(int a, int b) {
        return b == 0 ? a : GCD(b, a % b);
    }

    int dfs(int mask, int x) {
        if (x == n / 2 + 1) return 0;
        if (mask == (1 << n) - 1) return 0;
        if (dp[mask] != -1) return dp[mask];

        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (((mask >> i) & 1) != 0) {
                continue;
            }

            for (int j = i + 1; j < n; j++) {
                if (((mask >> j) & 1) != 0) {
                    continue;
                }

                sum = max(sum, x * gcds[i][j] + dfs(mask ^ (1 << i) ^ (1 << j), x + 1));
            }
        }
        dp[mask] = sum;
        return sum;
    }
};

dp

class Solution {
public:
    int maxScore(vector<int>& nums) {
        int m = nums.size();
        vector<int> dp(1 << m, 0);
        vector<vector<int>> gcd_tmp(m, vector<int>(m, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = i + 1; j < m; ++j) {
                gcd_tmp[i][j] = gcd(nums[i], nums[j]);
            }
        }
        int all = 1 << m;
        for (int s = 1; s < all; ++s) {
            // __builtin_popcount return 1 count numbers in s
            int t = __builtin_popcount(s);
            // 奇数不做处理
            if (t & 1) {
                continue;
            }
            for (int i = 0; i < m; ++i) {
                if ((s >> i) & 1) {
                    for (int j = i + 1; j < m; ++j) {
                        if ((s >> j) & 1) {
                            dp[s] = max(dp[s], dp[s ^ (1 << i) ^ (1 << j)] + t / 2 * gcd_tmp[i][j]);
                        }
                    }
                }
            }
        }
        return dp[all - 1];
    }
};