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
- State: a bitmask of the elements already used; the operation number is
popcount(mask) / 2 + 1. dp[mask]is the best score obtainable after consuming exactly the elements inmask.- Transition: for every unused pair
(i, j), updatedp[mask | bits]withdp[mask] + k * gcd(nums[i], nums[j]). - Since
n <= 7, the mask space is2^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
popcountinside the inner loops: compute it once per mask and reuse it. - Recomputing
gcdfor 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.