Skip to content

1799. Maximize Score After N Operations 👍

  • Time: $O(n^3 \cdot 2^n)$
  • Space: $O(n2^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;
    // dp[i][j] := max score of i to n operations with j mask
    dp.resize(n + 1, vector<int>(1 << n * 2));
    return maxScore(nums, 1, 0);
  }

 private:
  vector<vector<int>> dp;

  int maxScore(const vector<int>& nums, int op, int mask) {
    if (op == dp.size())
      return 0;
    if (dp[op][mask] > 0)
      return dp[op][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)
          dp[op][mask] =
              max(dp[op][mask], op * __gcd(nums[i], nums[j]) +
                                    maxScore(nums, op + 1, mask | chosenMask));
      }

    return dp[op][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;
    dp = new int[n + 1][1 << (n * 2)];
    return maxScore(nums, 1, 0);
  }

  private int[][] dp;

  private int maxScore(int[] nums, int op, int mask) {
    if (op == dp.length)
      return 0;
    if (dp[op][mask] > 0)
      return dp[op][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)
          dp[op][mask] = Math.max(dp[op][mask], op * gcd(nums[i], nums[j]) +
                                                    maxScore(nums, op + 1, mask | chosenMask));
      }

    return dp[op][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
class Solution:
  def maxScore(self, nums: List[int]) -> int:
    n = len(nums) // 2

    @functools.lru_cache(None)
    def dp(op: int, mask: int) -> int:
      if op == 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,
                      op * math.gcd(nums[i], nums[j]) + dp(op + 1, mask | chosenMask))

      return res

    return dp(1, 0)