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

Question

给你两个长度分别 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)

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

注意到 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)

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

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

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

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)$