⚡Flashcard Drill➔
NeetCode #700LC-1799Hard1-D Dynamic Programming
← Back to All Problems

#700 · #1799 · Maximize Score After N Operations(N 次操作后的最大分数和)

📌 Problem Statement & Constraints

Given nums of length 2 * n, perform n operations. In operation i (1-indexed) you pick two unused numbers a and b and gain i * gcd(a, b). Return the maximum total score. Constraints: 1 <= n <= 7, 2 <= 2 * n <= 14, 1 <= nums[i] <= 10^6.

💡 Core Algorithmic Approaches

  1. State: a bitmask of the elements already used; the operation number is popcount(mask) / 2 + 1.
  2. dp[mask] is the best score obtainable after consuming exactly the elements in mask.
  3. Transition: for every unused pair (i, j), update dp[mask | bits] with dp[mask] + k * gcd(nums[i], nums[j]).
  4. Since n <= 7, the mask space is 2^14 = 16384, which is tiny.

💻 Benchmark Python3 Implementation

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        from math import gcd
        n = len(nums)
        full = (1 << n) - 1
        dp = [0] * (1 << n)
        for mask in range(1 << n):
            k = bin(mask).count("1") // 2 + 1   # next operation number
            for i in range(n):
                if mask >> i & 1:
                    continue
                for j in range(i + 1, n):
                    if mask >> j & 1:
                        continue
                    nm = mask | (1 << i) | (1 << j)
                    dp[nm] = max(dp[nm], dp[mask] + k * gcd(nums[i], nums[j]))
        return dp[full]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(2^(2n) * n^2): for each mask we try every unused pair.
💾 Space Complexity
O(2^(2n)): the DP table.

⚠️ Interview Pitfalls & Follow-ups

  • Hard-coding the operation number: it must be derived from the mask as popcount(mask) / 2 + 1, otherwise the weighting is wrong.
  • Calling popcount inside the inner loops: compute it once per mask and reuse it.
  • Recomputing gcd for every pair at every mask: precomputing a gcd table indexed by the pair removes repeated work.
  • Reading the answer from a partial mask: every element must be consumed, so only dp[full] is terminal.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems