最大得分和

给定一个长度为 2n 的正整数数组 nums，你需要进行 n 次操作；

对于第 i 操作，你需要从数组 nums 中抽出两个正整数 a、b 不放回，并且得分记录为 gcd(a, b) * i；

请你求出进行了 n 次操作之后的最大得分之和。

完善代码

class Solution {
public:
    int maxScore(vector<int>& nums) {

    }
};

数据范围

\(1 \leq\) n \(\leq 7\)

\(1 \leq\) nums[i] \(\leq 10 ^ 6\)

记忆化搜索

代码参考

class Solution {
public:

    int n;
    int a[100], st[100];
    int dp[100][100][100];

    int gcd(int a, int b)
    {
        if (!a || !b) return a | b;
        else return a > b ? gcd(b, a % b) : gcd(a, b % a);
    }

    int dfs(int x, int y, int f)
    {
        if (f > n) return 0;
        if (dp[x][y][n]) return dp[x][y][n];
        int res = 0;
        for (int i = 0; i < n; i ++)
        {
            if (st[i]) continue;
            st[i] = 1;
            for (int j = 0; j < n; j ++)
            {
                if (st[j]) continue;
                st[j] = 1;
                res = max(res, dfs(i, j, f + 1));
                st[j] = 0;
            }
            st[i] = 0;
        }
        return dp[x][y][f] = gcd(a[x], a[y]) * f + res;
    }

    int maxScore(vector<int>& nums) {
        n = nums.size();
        for (int i = 0; i < n; i ++) a[i] = nums[i];
        memset(st, 0, sizeof st);
        memset(dp, 0, sizeof dp);
        return dfs(0, 0, 0);
    }
};