Description
給定長度為
2n的正整數陣列nums，執行n次操作。第i次操作（1-indexed）選兩個元素，得分為i * gcd(選的兩個數)。求最大總得分。
Example:
Input: nums = [1,2] Output: 1
Intuition#
用 bitmask 表示已使用的元素，DP 枚舉每次操作選擇的配對。
2n <= 14，所以最多 14 個元素，bitmask 最多2^14 = 16384種狀態dp[mask]= 已使用 mask 中的元素時能獲得的最大得分- 當前操作編號 =
popcount(mask) / 2 + 1 - 枚舉所有未使用的元素配對
Approaches#
1: Top-Down Bitmask DP#
- 概念: 記憶化搜尋，每次選兩個未使用的元素配對
- 時間複雜度:
O(2^(2n) * n^2) - 空間複雜度:
O(2^(2n))
class Solution {
fun maxScore(nums: IntArray): Int {
val n = nums.size
val memo = IntArray(1 shl n) { -1 }
fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
fun dp(mask: Int): Int {
if (memo[mask] != -1) return memo[mask]
val op = Integer.bitCount(mask) / 2 + 1
var best = 0
for (i in 0 until n) {
if (mask and (1 shl i) != 0) continue
for (j in i + 1 until n) {
if (mask and (1 shl j) != 0) continue
val newMask = mask or (1 shl i) or (1 shl j)
val score = op * gcd(nums[i], nums[j]) + dp(newMask)
best = maxOf(best, score)
}
}
memo[mask] = best
return best
}
return dp(0)
}
}⭐2: Bottom-Up Bitmask DP with GCD Precomputation#
- 概念: 預計算所有配對的 GCD，自底向上填表
- 時間複雜度:
O(2^(2n) * n^2) - 空間複雜度:
O(2^(2n) + n^2)
class Solution {
fun maxScore(nums: IntArray): Int {
val n = nums.size
fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
// 預計算所有配對的 GCD
val gcdTable = Array(n) { i -> IntArray(n) { j -> gcd(nums[i], nums[j]) } }
val dp = IntArray(1 shl n)
for (mask in 0 until (1 shl n)) {
val bits = Integer.bitCount(mask)
if (bits % 2 != 0) continue
val op = bits / 2 + 1
for (i in 0 until n) {
if (mask and (1 shl i) != 0) continue
for (j in i + 1 until n) {
if (mask and (1 shl j) != 0) continue
val newMask = mask or (1 shl i) or (1 shl j)
dp[newMask] = maxOf(dp[newMask], dp[mask] + op * gcdTable[i][j])
}
}
}
return dp[(1 shl n) - 1]
}
}🔑 Takeaways#
- Pattern: Bitmask DP 配對問題 — 用位元遮罩追蹤已使用的元素，枚舉配對
- 關鍵技巧: 操作編號可由
popcount / 2推算出來，不需額外參數；預計算 GCD 表避免重複計算