Skip to content

1799. Maximize Score After N Operations 👍

  • Time: $O(n^3 \cdot 2^n)$
  • Space: $O(n \cdot 2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  int maxScore(vector<int>& nums) {
    const int n = nums.size() / 2;
    vector<vector<int>> mem(n + 1, vector<int>(1 << n * 2));
    return maxScore(nums, 1, 0, mem);
  }

 private:
  // Returns the maximum score you can receive after performing the k to n
  // operations, where `mask` is the bitmask of the chosen numbers.
  int maxScore(const vector<int>& nums, int k, int mask,
               vector<vector<int>>& mem) {
    if (k == mem.size())
      return 0;
    if (mem[k][mask] > 0)
      return mem[k][mask];

    for (int i = 0; i < nums.size(); ++i)
      for (int j = i + 1; j < nums.size(); ++j) {
        const int chosenMask = 1 << i | 1 << j;
        if ((mask & chosenMask) == 0)
          mem[k][mask] = max(mem[k][mask],
                             k * __gcd(nums[i], nums[j]) +
                                 maxScore(nums, k + 1, mask | chosenMask, mem));
      }

    return mem[k][mask];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public int maxScore(int[] nums) {
    final 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.length)
      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) {
        final 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);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
  def maxScore(self, nums: List[int]) -> int:
    n = len(nums) // 2

    @functools.lru_cache(None)
    def dp(k: int, mask: int) -> int:
      """
      Returns the maximum score you can receive after performing the k to n
      operations, where `mask` is the bitmask of the chosen numbers.
      """
      if k == n + 1:
        return 0

      res = 0

      for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
          chosenMask = 1 << i | 1 << j
          if (mask & chosenMask) == 0:
            res = max(res,
                      k * math.gcd(nums[i], nums[j]) + dp(k + 1, mask | chosenMask))

      return res

    return dp(1, 0)