What is the optimal approach for maximizing score in the "Maximize Score After N Operations" problem?

The optimal approach is state transition dynamic programming, where you explore all possible pairings of elements in the array while maximizing the score based on their GCD values.

Can backtracking be used to solve this problem?

Yes, backtracking can be used with memoization to efficiently explore all possible pairings while avoiding redundant calculations.

How does bitmasking help in solving the "Maximize Score After N Operations" problem?

Bitmasking allows you to represent which elements have been paired, making it easier to explore all valid pair combinations and calculate the maximum score.

What is the time complexity of the optimal solution?

The time complexity of the optimal solution using dynamic programming with bitmasking is O(n * 2^n), where n is the size of the array.

How can I avoid redundant calculations in this problem?

Memoization and backtracking are key to avoiding redundant calculations by storing intermediate results and only recalculating when necessary.

#1799

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

N 次操作后的最大分数和

给你 nums ，它是一个大小为 2 * n 的正整数数组。你必须对这个数组执行 n 次操作。在第 i 次操作时（操作编号从 1 开始），你需要：选择两个元素 x 和 y 。获得分数 i * gcd(x, y) 。将 x 和 y 从 nums 中删除。请你返回 n 次操作后你能获得的分数和…

数组数学动态规划回溯位运算

题目描述

给你 nums ，它是一个大小为 2 * n 的正整数数组。你必须对这个数组执行 n 次操作。

在第 i 次操作时（操作编号从 1 开始），你需要：

选择两个元素 x 和 y 。
获得分数 i * gcd(x, y) 。
将 x 和 y 从 nums 中删除。

请你返回 n 次操作后你能获得的分数和最大为多少。

函数 gcd(x, y) 是 x 和 y 的最大公约数。

示例 1：

输入：nums = [1,2]
输出：1
解释：最优操作是：
(1 * gcd(1, 2)) = 1

示例 2：

输入：nums = [3,4,6,8]
输出：11
解释：最优操作是：
(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11

示例 3：

输入：nums = [1,2,3,4,5,6]
输出：14
解释：最优操作是：
(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14

提示：

1 <= n <= 7
nums.length == 2 * n
1 <= nums[i] <= 10⁶

lightbulb

解题思路

方法一：状态压缩 + 动态规划

我们可以先预处理得到数组 nums 中任意两个数的最大公约数，存储在二维数组 $g$ 中，其中 $g[i][j]$ 表示 $nums[i]$ 和 $nums[j]$ 的最大公约数。

然后定义 $f[k]$ 表示当前操作后的状态为 $k$ 时，可以获得的最大分数和。假设 $m$ 为数组 nums 中的元素个数，那么状态一共有 $2^m$ 种，即 $k$ 的取值范围为 $[0, 2^m - 1]$ 。

从小到大枚举所有状态，对于每个状态 $k$ ，先判断此状态的二进制位中 $1$ 的个数 $cnt$ 是否为偶数，是则进行如下操作：

枚举 $k$ 中二进制位为 1 的位置，假设为 $i$ 和 $j$ ，则 $i$ 和 $j$ 两个位置的元素可以进行一次操作，此时可以获得的分数为 $\frac{cnt}{2} \times g[i][j]$ ，更新 $f[k]$ 的最大值。

最终答案即为 $f[2^m - 1]$ 。

时间复杂度 $O(2^m \times m^2)$ ，空间复杂度 $O(2^m)$ 。其中 $m$ 为数组 nums 中的元素个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        m = len(nums)
        f = [0] * (1 << m)
        g = [[0] * m for _ in range(m)]
        for i in range(m):
            for j in range(i + 1, m):
                g[i][j] = gcd(nums[i], nums[j])
        for k in range(1 << m):
            if (cnt := k.bit_count()) % 2 == 0:
                for i in range(m):
                    if k >> i & 1:
                        for j in range(i + 1, m):
                            if k >> j & 1:
                                f[k] = max(
                                    f[k],
                                    f[k ^ (1 << i) ^ (1 << j)] + cnt // 2 * g[i][j],
                                )
        return f[-1]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check for the candidate's ability to apply dynamic programming in combinatorial problems.
question_mark
Assess how efficiently the candidate handles memoization and backtracking to reduce computational overhead.
question_mark
Look for understanding of bitmasking techniques and how it can be applied to problems involving subsets.

warning

常见陷阱

外企场景

error
Failing to efficiently memoize subproblems, leading to redundant recalculations.
error
Not correctly handling the state transitions in dynamic programming, which can cause incorrect results or excessive time complexity.
error
Overcomplicating the problem with unnecessary optimizations or not fully exploring all pairings.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider the problem with different constraints, such as larger arrays or additional scoring rules.
arrow_right_alt
Allow multiple solutions for pairing, where the goal could be to find the second-highest score instead of the maximum.
arrow_right_alt
Modify the problem to return all possible score configurations and have the candidate find the one with the maximum score.

help

常见问题

外企场景

继续练习

#1994 好子集的数目 #996 平方数组的数目 #1255 得分最高的单词集合