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 步， 所能获得的最大分数。
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)上面代码非常好写，复杂度为
注意到 steps 其实可以根据 i 和 j 推导出来。因为每一步我们必定要选择一次，这是关键。那么我们当前选择了多少就可以根据 i 和 j 推导出来， 这样就可以降低到二维 dp[i][j]。代码：
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)不过代入后还是远远大于
小技巧，下面的代码可以通过，不过也不推荐。
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。
显然这种方式枚举的时间复杂度为
- 维度选择
- 降维
- 语言支持：Python3
Python3 Code:
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)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
大家也可以看下力扣国际站的官方题解