# 1770. 执行乘法运算的最大分数

### 题目地址(1770. 执行乘法运算的最大分数)

<https://leetcode.cn/problems/maximum-score-from-performing-multiplication-operations/>

### 题目描述

```
给你两个长度分别 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.length
m == multipliers.length
1 <= m <= 103
m <= n <= 105
-1000 <= nums[i], multipliers[i] <= 1000
```

### 前置知识

* 动态规划
* 区间动态规划

### 公司

* 暂无

### 思路

这是一个典型的区间 DP 问题。

直接套用区间 DP 的公，定义 DP\[i]\[j] 为考虑区间 nums\[i:j] 的情况下， 所能获得的最大分数。

那么我们有两个选择， 取左端点或者取右端点，这两种选择取最大值即可。同时需要一个变量记录当前是第几步操作， 以便知道要乘以多少。

这样 dp\[i]\[j]\[steps] 就表示考虑区间 nums\[i:j] 的情况下当前是第 steps 步， 所能获得的最大分数。

```py
class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        @cache
        def dp(i, j, steps):
            if steps == len(multipliers): return 0
            return max(dp(i + 1, j, steps + 1) + multipliers[steps] * nums[i], dp(i, j - 1, steps + 1) + multipliers[steps] * nums[j])
        return dp(0, len(nums) - 1, 0)
```

上面代码非常好写，复杂度为 $O(m\*n^2)$但是会严重超时。代入题目中的数据 m 为 10^3, n 为 10 ^ 5，那么整体就是 $10^13$， 远远大于 $10^7$ 这个临界值。

注意到 steps 其实可以根据 i 和 j 推导出来。因为每一步我们必定要选择一次，这是关键。那么我们当前选择了多少就可以根据 i 和 j 推导出来， 这样就可以降低到二维 dp\[i]\[j]。代码：

```py
class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        @cache
        def dp(i, j):
            steps = len(nums) - (j - i + 1)
            if steps == len(multipliers): return 0
            return max(dp(i + 1, j) + multipliers[steps] * nums[i], dp(i, j - 1,) + multipliers[steps] * nums[j])
        return dp(0, len(nums) - 1)
```

不过代入后还是远远大于 $10^7$ 这个临界值。

小技巧，下面的代码可以通过，不过也不推荐。

```py
class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        @cache
        def dp(i, j):
            steps = len(nums) - (j - i + 1)
            if steps == len(multipliers): return 0
            return max(dp(i + 1, j) + multipliers[steps] * nums[i], dp(i, j - 1,) + multipliers[steps] * nums[j])
        ans = dp(0, len(nums) - 1)
        dp.cache_clear()
        return ans
```

这里要使用到一种技巧 - 维度选择。

我们可以换一种状态定义方式，即思考 mutlipiers， 因为它的数据量小（题目给的是 10 ^ 3）。

实际上，我们可以定义 dp\[i]\[j] 为选择 nums 前 i 项目和 nums 后 j 项目可以获得的最大分数（题目限制了只能取左右两端）。但是注意到 i 和 j 一定是要小于 m 的， 因为不妨直接枚举到 m 即可， 而不需要枚举到 n。

显然这种方式枚举的时间复杂度为 $O(m^2)$，代入题目大概是 $10^6$ , 小于临界值 $10^7$。

### 关键点

* 维度选择
* 降维

### 代码

* 语言支持：Python3

Python3 Code:

```python

class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        n,m=len(nums),len(multipliers)
        dp=[[float('-inf')]*(m+1) for _ in range(m+1)]
        dp[0][0]=0
        ans=float('-inf')
        for i in range(1,m+1): # 枚举长度
            for l in range(i+1): # 枚举左侧取了 l 个
                r = i - l # 右侧取的就是总数 -  左边取的
                dp[l][r]=max(dp[l][r],dp[l-1][r]+nums[l-1]*multipliers[i-1], dp[l][r-1]+nums[-r]*multipliers[i-1])
                if i == m: ans=max(ans,dp[l][r])
        return ans


```

**复杂度分析**

令 n 为数组长度。

* 时间复杂度：$O(n^2)$
* 空间复杂度：$O(n^2)$

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/uh3k7s.jpg)

### 其他

大家也可以看下[力扣国际站的官方题解](https://leetcode.com/problems/maximum-score-from-performing-multiplication-operations/solution/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1770.maximum-score-from-performing-multiplication-operations.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.