【20221222】每日一题

【LC1799】

class Solution {
public:
    int n;
    vector<int> dp; //状态DP;
    vector<vector<int>> gcd; //gcd<i, j>:nums[i], nums[j] gcd的结果;

    int GCD(int x, int y)
    {
        return y == 0 ? x : GCD(y, x % y);
    }

    int maxScore(vector<int>& nums) {
        n = nums.size();
        dp.resize(1 << n, 0);
        gcd.resize(n, vector<int>(n , 0));
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                gcd[i][j] = GCD(nums[i], nums[j]);
            }

        return dfs(1, (1 << n) - 1, 0, nums);
    }

    int dfs(int idx, int mask, int sum, vector<int>& nums)
    {
        //因为不可能超过一半size,gcd的对称性;
        if (idx >= n / 2 + 1) return sum;
        //若是已经被处理过，则直接使用之前的结果;
        if (dp[mask] > 0) return sum + dp[mask];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (((1 << i) & mask ) == 0) continue;
            for (int j = i + 1; j < n; j++) {
                if (((1 << j) & mask) == 0) continue;
                int next_state = mask^(1 << i) ^ ( 1<< j);
                ans = max(ans, dfs(idx + 1, next_state, sum + idx * gcd[i][j], nums));
            }
        }

        dp[mask] = ans - sum;   
        return ans;
    }
};

基本思路是状态DP + DFS记忆化搜索，关键在于n的取值得到的。