1799. Maximize Score After N Operations
Approach
Bitmask DP — enumerate pair selections; dp[mask] = max score using pairs indicated by set bits.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.
Dynamic programming solves problems by breaking them into overlapping sub-problems and storing results to avoid redundant work. The key steps are: define state, write a recurrence relation, set base cases, and choose top-down (memoization) or bottom-up (tabulation). DP often yields O(n²) → O(n) time improvements over brute force.
// Approach: Bitmask DP — enumerate pair selections; dp[mask] = max score using pairs indicated by set bits.
// Time: O(n² * 2^(2n)) Space: O(2^(2n))
public class Solution
{
public int MaxScore(int[] nums)
{
int n = nums.Length / 2;
int[,] mem = new int[n + 1, 1 << (n * 2)];
return MaxScore(nums, 1, 0, mem);
}
// Returns the maximum score you can receive after performing the k to n
// operations, where `mask` is the bitmask of the chosen numbers.
private int MaxScore(int[] nums, int k, int mask, int[,] mem)
{
if (k == mem.GetLength(0))
return 0;
if (mem[k, mask] > 0)
return mem[k, mask];
for (int i = 0; i < nums.Length; ++i)
{
for (int j = i + 1; j < nums.Length; ++j)
{
int chosenMask = (1 << i) | (1 << j);
if ((mask & chosenMask) == 0)
mem[k, mask] = Math.Max(mem[k, mask], k * Gcd(nums[i], nums[j]) +
MaxScore(nums, k + 1, mask | chosenMask, mem));
}
}
return mem[k, mask];
}
private int Gcd(int a, int b)
{
return b == 0 ? a : Gcd(b, a % b);
}
}