1799. Maximize Score after N Operations

解法已隱藏 — 先讀題目敘述、自己想想看，再點上方按鈕揭曉。

1799Maximize Score after N Operations1-D DPHard1-D DP

給定長度為 2n 的正整數陣列 nums，執行 n 次操作。第 i 次操作（1-indexed）選兩個元素，得分為 i * gcd(選的兩個數)。求最大總得分。

Example:

Input: nums = [1,2] Output: 1

Intuition

TIP

用 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))

Idea: 記憶化搜尋，每次選兩個未使用的元素配對
Time: O(2^(2n) * n^2)
Space: 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 — O(2^(2n) * n^2) / O(2^(2n) + n^2)

Idea: 預計算所有配對的 GCD，自底向上填表
Time: O(2^(2n) * n^2)
Space: 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 配對問題 — 用位元遮罩追蹤已使用的元素，枚舉配對
Key trick: 操作編號可由 popcount / 2 推算出來，不需額外參數；預計算 GCD 表避免重複計算

Intuition

Approaches

🔑 Takeaways

相關題目