https://leetcode.com/problems/maximize-score-after-n-operations/

這題一開始我用 greedy 的方式做，寫完才發現 greedy 事實上會錯。

首先，這一題需要知道所有的子集的最佳解。也就是要知道經過 1 次操作後的各種組合最佳解，然後再用這個結果推到經過 2 次操作後的各種組合最佳解。以此類推，直到找到經過 n / 2 次操作後的最佳解。

例如 nums = [1,2,3,4,5,6]。用 6 個 bit 來記錄選了哪些數字。
$110000_2$ 就是代表「在只有第 3, 4, 5, 6 個數字可以選的情況下，此時最佳解」。並且用 dp[$110000_2$] 來記錄這個結果。\

假設想要求 dp[$110000_2$]，也就是「第 3, 4, 5, 6 個數字可以選的情況下，此時最佳解」，有以下的選擇：

1. 選第 3, 4 個數字，結果會是 2 * gcd(nums[3], nums[4]) + dp[$111100_2$]
2. 選第 3, 5 個數字，結果會是 2 * gcd(nums[3], nums[5]) + dp[$111010_2$]
3. 選第 3, 6 個數字，結果會是 2 * gcd(nums[3], nums[6]) + dp[$111001_2$]
4. 選第 4, 5 個數字，結果會是 2 * gcd(nums[4], nums[5]) + dp[$110110_2$]
5. 選第 4, 6 個數字，結果會是 2 * gcd(nums[4], nums[6]) + dp[$110101_2$]
6. 選第 5, 6 個數字，結果會是 2 * gcd(nums[5], nums[6]) + dp[$110011_2$]

dp[$110000_2$] 就是上面這些選擇的最大值。
之所以是 2 * gcd(x, y)，是因爲 $110000_2$ 有 4 個 0，所以選數字的話，會是第 2 次選（4 / 2 = 2）。

但是問題是，要怎麼知道哪些數字可以選，哪些不行呢？

這時候可以用兩個 for loop 來遍歷這些 bit，

1
2
3

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        int pick = (1 << i) + (1 << j);

如果 pick 跟當前的選擇 state 做 & operation 爲 0，那就代表這是一個合法的選擇。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int maxScore(vector<int>& nums) {
    int n = nums.size();
    int k = n / 2;
    vector<int> memo(1 << n, 0);
    function<int(int)> dp = [&](int state){
        if (state == (1 << n) - 1){
            return 0;
        }
        if (memo[state] > 0){
            return memo[state];
        }
        for (int i = 0; i < n; i++){
            for (int j = i + 1; j < n; j++){
                int pick = (1 << i) + (1 << j);
                if ((pick & state) == 0){
                    int ones = __builtin_popcount(state);
                    int ith = (n - ones) / 2;
                    memo[state] = max(memo[state], gcd(nums[i], nums[j]) * ith + dp(state + pick));
                }
            }
        }
        return memo[state];
    };
    return dp(0);
}

state == (1 << n) - 1 代表 state 是全部爲 1 的數字，也就是沒有任何數字可以選，此時回傳 0。
ith = (n - ones) / 2 就是計算當前的操作是第幾次操作，也就是 0 bit 的數量除以 2。

time complexity: $2^n \times n^2$
space complextiy: $2^n$

或是也可以用 Gosper’s Hack 直接找到有偶數個 1 的所有組合，然後做類似的操作，也可以解出這一題。