主題
題目連結：
題目意譯：
你被給定 nums，其為一個正整數陣列且大小為 2 × n。你必須在該陣列上執行 n 次操作。
在第 i 次操作（索引值從 1 開始），你將：
選出兩個元素 x 和 y、
得到一個分數值 i × gcd(x, y)、
將 x 和 y 從 nums 中移除。
回傳執行 n 次操作後你可以得到的最大分數值。
函式 gcd(x, y) 代表著 x 和 y 的最大公因數（Greatest Common Divisor）。
限制：
1 ≦ n ≦ 7
nums.length == 2 × n
1 ≦ nums[i] ≦ 10 ^ 6
範例測資：
範例 1：
輸入： nums = [1,2]
輸出： 1
解釋： 最佳選擇為：
(1 × gcd(1, 2)) = 1
範例 2：
輸入： nums = [3,4,6,8]
輸出： 11
解釋： 最佳選擇為：
(1 × gcd(3, 6)) + (2 × gcd(4, 8)) = 3 + 8 = 11
範例 3：
輸入： nums = [1,2,3,4,5,6]
輸出： 14
解釋： 最佳選擇為：
(1 × gcd(1, 5)) + (2 × gcd(2, 4)) + (3 × gcd(3, 6)) = 1 + 4 + 9 = 14
解題思維：
以前談到旅行推銷員問題（Travelling Salesman Problem，TSP）的時候有把有無被探訪過的「狀態」簡化成一個二進位數字（中文圈通稱其為狀態壓縮。似乎沒有相應的英文字詞）。
而在本題，我們可以做類似的事情——即使用一個二進位數字來代表「現在」選過（或沒選過）哪些數字。
假設現在已經選了某些數字。則我們將會產生出一些子問題，即「接下來要先選哪些數字」。
此時我們便可以直接套用動態規劃的精神——不知道要做哪些子問題，那就全做吧！（誠如之前所述）
因此定義一個陣列 D，其中 D[i] 代表著在挑選狀態為 i（此即上面所述用於表示狀態用之數字）的情況下，剩下的數字可以得到的最大分數值。可以看到其遞迴式為：
D[2 ^ (2n) - 1] = 0
（此為遞迴停止條件。其中 2 ^ (2n) - 1 為一個有著 2n 個 1 之二進位數字，即代表著所有數字已經被挑選過）
D[i] = max(D[i + (2 ^ j) + (2 ^ k)] + gcd(nums[j], nums[k]) × C)，其中 0 ≦ i < 2 ^ (2n) - 1 、 0 ≦ j < k < 2n 且 C 代表著「現在」是第幾次操作。可以看到 C 跟 i 中的 1 之數量相對應——假設現在 i 中有 x 個 1，則 C == (x ÷ 2) + 1。
因此從 D[0] 開始遞迴（記得已經求過的子問題就不用再重求一次了，直接使用之前算過的值即可）便可以得到所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
