# 1770. 执行乘法运算的最大分数
### 题目地址(1770. 执行乘法运算的最大分数)
### 题目描述
```
给你两个长度分别 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 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
### 其他
大家也可以看下[力扣国际站的官方题解](https://leetcode.com/problems/maximum-score-from-performing-multiplication-operations/solution/)