LeetCode 题解工作台
执行乘法运算的最大分数
给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ，其中 n >= m ，数组下标 从 1 开始 计数。 初始时，你的分数为 0 。你需要执行恰好 m 步操作。在第 i 步操作（ 从 1 开始 计数）中，需要： 选择数组 nums 开头处或者末尾处 的整数 x 。 你获…
2
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们设计一个函数 $dfs(i, j)$，表示从 `nums` 数组头部第 个元素开始，从 `nums` 数组尾部第 个元素开始，能够获得的最大分数。那么答案就是 $dfs(0, 0)$。 函数 $dfs(i, j)$ 的计算过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ，其中 n >= m ，数组下标 从 1 开始 计数。
初始时，你的分数为 0 。你需要执行恰好 m 步操作。在第 i 步操作（从 1 开始 计数）中，需要：
- 选择数组
nums开头处或者末尾处 的整数x。 - 你获得
multipliers[i] * x分，并累加到你的分数中。 - 将
x从数组nums中移除。
在执行 m 步操作后，返回 最大 分数。
示例 1：
输入：nums = [1,2,3], multipliers = [3,2,1] 输出：14 解释：一种最优解决方案如下： - 选择末尾处的整数 3 ，[1,2,3] ，得 3 * 3 = 9 分，累加到分数中。 - 选择末尾处的整数 2 ，[1,2] ，得 2 * 2 = 4 分，累加到分数中。 - 选择末尾处的整数 1 ，[1] ，得 1 * 1 = 1 分，累加到分数中。 总分数为 9 + 4 + 1 = 14 。
示例 2：
输入：nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6] 输出：102 解释：一种最优解决方案如下： - 选择开头处的整数 -5 ，[-5,-3,-3,-2,7,1] ，得 -5 * -10 = 50 分，累加到分数中。 - 选择开头处的整数 -3 ，[-3,-3,-2,7,1] ，得 -3 * -5 = 15 分，累加到分数中。 - 选择开头处的整数 -3 ，[-3,-2,7,1] ，得 -3 * 3 = -9 分，累加到分数中。 - 选择末尾处的整数 1 ，[-2,7,1] ，得 1 * 4 = 4 分，累加到分数中。 - 选择末尾处的整数 7 ，[-2,7] ，得 7 * 6 = 42 分，累加到分数中。 总分数为 50 + 15 - 9 + 4 + 42 = 102 。
提示：
n == nums.lengthm == multipliers.length1 <= m <= 103m <= n <= 105-1000 <= nums[i], multipliers[i] <= 1000
解题思路
方法一：记忆化搜索
我们设计一个函数 ，表示从 nums 数组头部第 个元素开始，从 nums 数组尾部第 个元素开始，能够获得的最大分数。那么答案就是 。
函数 的计算过程如下：
- 如果 或者 ，或者 ，说明已经没有元素可以选择了，返回 。
- 否则，我们可以选择
nums数组头部第 个元素，那么能够获取的最大分数为 ；或者我们可以选择nums数组尾部第 个元素，那么能够获取的最大分数为 。我们取两者的最大值作为 的返回值。
我们可以使用记忆化搜索来实现上述递归过程，其中 f 数组用于存储函数 的返回值，防止重复计算。
时间复杂度 ，空间复杂度 。其中 为 multipliers 数组的长度。
class Solution:
def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
@cache
def f(i, j, k):
if k >= m or i >= n or j < 0:
return 0
a = f(i + 1, j, k + 1) + nums[i] * multipliers[k]
b = f(i, j - 1, k + 1) + nums[j] * multipliers[k]
return max(a, b)
n = len(nums)
m = len(multipliers)
return f(0, n - 1, 0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's ability to recognize dynamic programming patterns.
- question_mark
Assess how well the candidate manages state transitions between operations.
- question_mark
Evaluate their ability to optimize space complexity while maintaining correctness.
常见陷阱
外企场景- error
Choosing elements greedily from the start or end can lead to suboptimal solutions.
- error
Not properly managing the dynamic programming table may result in incorrect score calculations.
- error
Failing to optimize space complexity when using a 2D DP table can lead to unnecessary memory usage.
进阶变体
外企场景- arrow_right_alt
Modify the problem to include negative multipliers, affecting the strategy for selecting elements.
- arrow_right_alt
Increase the size of the nums array to test the scalability of the solution.
- arrow_right_alt
Change the problem to allow multiple operations with different ranges of multipliers.