LeetCode 1770. 执行乘法运算的最大分数
题目描述
给定长度为n的整数数组nums，以及长度为m的系数数组multipliers，m≤n。第i轮从nums当前左端或右端取一个数x，获得multipliers[i]×x分。恰好取m次，返回最大总分。允许负数；原题m≤300、n≤100000，元素绝对值不超过1000。
示例 1：
输入：nums = [1,2,3], multipliers = [3,2,1]
输出：14
解释：依次从右端取 3、2、1，得分为 3×3+2×2+1×1=14。
提示：
- 1≤m≤300，m≤n≤100000；两个数组的元素绝对值均不超过 1000。恰好执行 m 轮，系数按输入顺序使用。
题意分析
有长度为
n的数组nums和长度为m的系数数组。每轮只能取当前剩余数组的左端或右端，乘以这一轮的系数后加入总分，并从数组中移除所取元素。必须恰好完成m轮，系数按原顺序使用。数组值和系数都可能为负，不能只选当前较大的端点或较大的即时乘积。当前选择还会改变后续可用的两端，需要比较完成全部剩余轮次后的总收益。
m比n小得多时，状态应围绕操作次数建立，而不是给全部原数组区间开表。
解法：按轮次与左取数量压缩状态
核心思路
[!blue]
执行过
i轮后，如果其中left次从左端取数，那么从右端取走的数量必定是i - left。剩余左端下标就是left，右端下标就是n - 1 - (i - left)。操作次数和左取数量已经唯一确定当前可选区间，无须再存第三个右端状态。先把二维状态理解为
F(i, left)：已经完成i轮、左端取过left个时，完成后续全部轮次还能获得的最大分数。取左端时，本轮得分为nums[left] * multipliers[i]，后继是F(i + 1, left + 1)；取右端时使用推算出的右端下标，后继是F(i + 1, left)。两种选择取最大值。当
i = m时，所有规定操作都已完成，后续收益为零。按i从m - 1向零计算，每轮只依赖下一轮，因此可以用一个长度为m + 1的dp数组保存上一批已算好的后缀收益。原地覆盖时，
left必须从小到大。更新dp[left]需要旧的dp[left]和旧的dp[left + 1]；正序时右边一项尚未改写，两者都仍表示i + 1轮的状态。若反向更新，右边一项就会变成本轮状态，混淆剩余操作数量。每轮只计算
0 <= left <= i，因为完成i次操作后不可能从左端取超过i个。初始全零代表“完成全部轮次”的合法终点，不是允许中途停止；即使所有后续选择得分为负，也必须通过其中一条转移继续完成规定次数。计算回
i = 0时，尚未从左端取数，最终答案就是dp[0]。
解题步骤
- 创建
m + 1项全零数组，表示所有轮次结束后的收益。- 倒序枚举轮次
i，再按left = 0到i递增枚举已从左边取出的数量。- 用总取数减去左取数，推算当前右端下标。
- 分别计算取左、取右的本轮分数加下一轮最优收益，取最大值写回
dp[left]。- 返回
dp[0]。
代码实现
class Solution {
public int maximumScore(int[] nums, int[] multipliers) {
int n = nums.length;
int m = multipliers.length;
long[] dp = new long[m + 1];
for (int i = m - 1; i >= 0; i--) {
for (int left = 0; left <= i; left++) {
int right = n - 1 - (i - left);
dp[left] =
Math.max(
(long) nums[left] * multipliers[i] + dp[left + 1],
(long) nums[right] * multipliers[i] + dp[left]);
}
}
return (int) dp[0];
}
}
func maximumScore(nums, multipliers []int) int {
n, m := len(nums), len(multipliers)
dp := make([]int64, m+1)
for i := m - 1; i >= 0; i-- {
for left := 0; left <= i; left++ {
right := n - 1 - (i - left)
dp[left] = max(int64(nums[left])*int64(multipliers[i])+dp[left+1], int64(nums[right])*int64(multipliers[i])+dp[left])
}
}
return int(dp[0])
}
复杂度分析
- 时间复杂度：$O(m^2)$，每轮计算
i + 1个状态，总状态数为 $1+2+\cdots+m$，每个状态只有两种选择。- 空间复杂度：$O(m)$，只保存下一轮到当前轮复用的一维收益表，不按可能很大的
n建区间表。
关键点总结
[!green]
- 左取数加右取数等于已完成轮次，利用这个关系消去一个状态维度。
- 系数下标由操作轮次决定，原数组左右端下标则由两侧已取数量决定。
- 轮次倒序、左取数量正序，分别保证依赖已计算和原地更新不污染旧值。
- 零收益只属于全部操作结束的状态，不能用它跳过负分轮次。
易错点总结
[!yellow]
- 右端下标漏掉
i - left，会使用已经取走的元素，或误把左取数当作右取数。- 用原数组位置选择系数，忽略系数固定按第几轮使用。
- 一维更新时让
left递减，会读取已经覆盖成本轮的右侧状态。- 每次只贪心选较大端点，无法处理负系数，也没有考虑后续轮次的取数机会。
- 与零取最大来避免负收益，相当于允许提前结束，违反必须取满
m次的要求。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 486. 预测赢家 | 中等 | 都比较取左或取右，但原题考虑对手最优反应，本题只有一个决策者并使用轮次系数。 |