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 步, 所能获得的最大分数。

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

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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

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

其他

大家也可以看下力扣国际站的官方题解

最后更新于