执行乘法运算的最大分数

难度: Hard

给你两个长度分别 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 <= 10³
m <= n <= 10⁵
-1000 <= nums[i], multipliers[i] <= 1000

Submission

运行时间: 252 ms

内存: 24.6 MB

class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        m=len(multipliers)
        n=len(nums)
        dp=[0]
        for i,v in enumerate(multipliers):
            ndp=[0]*(i+2)
            for j in range(i+2):
                if j==0:
                    ndp[j]=dp[j]+v*nums[-(i+1-j)]
                elif j<i+1:
                    ndp[j]=max(dp[j-1]+v*nums[j-1],dp[j]+v*nums[-(i+1-j)])
                else:
                    ndp[j]=dp[j-1]+v*nums[j-1]
            dp=ndp 

        return max(dp)

Explain

本题解采用动态规划的方法处理问题。定义 dp[j] 表示在第 i 步操作后，从 nums 数组的前 j 个元素和后 (i+1-j) 个元素中选择元素所能得到的最大分数。数组 ndp 用于更新下一步的分数。对于每一个操作 i，我们可以选择 nums 数组的开头或结尾的元素，因此需要更新 ndp[j]，其中 j 表示选择的元素数量。如果 j==0，我们只选择了末尾的元素；如果 j 在 1 到 i 之间，可以选择开头或末尾的元素；如果 j==i+1，我们只选择开头的元素。通过这种方式，我们可以在每一步中寻找最大分数的可能性。

时间复杂度: O(m^2)

空间复杂度: O(m)

class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        m = len(multipliers)
        n = len(nums)
        dp = [0]
        for i, v in enumerate(multipliers):
            ndp = [0] * (i + 2)  # 创建一个新的 dp 数组
            for j in range(i + 2):
                if j == 0:
                    ndp[j] = dp[j] + v * nums[-(i + 1 - j)]  # 只选择末尾元素
                elif j < i + 1:
                    ndp[j] = max(dp[j - 1] + v * nums[j - 1], dp[j] + v * nums[-(i + 1 - j)])  # 选择开头或末尾元素
                else:
                    ndp[j] = dp[j - 1] + v * nums[j - 1]  # 只选择开头元素
            dp = ndp  # 更新 dp 数组

        return max(dp)  # 返回最大分数

Explore

这个问题涉及到多个选择的阶段，每个阶段都需要做出选择，这些选择会影响到最终的结果。动态规划适合用于解决这种具有重叠子问题和最优子结构的问题。使用贪心算法可能不会得到全局最优解，因为每个阶段的局部最优选择可能不会导致全局最优。而回溯算法虽然可以遍历所有可能的解空间以找到最优解，但其时间复杂度通常很高，不适合处理大规模数据。动态规划通过保存子问题的解，避免重复计算，以较高的空间复杂度换取时间效率，更适合此类问题。

状态转移方程的确定基于问题的具体要求。在这个问题中，我们的目标是最大化使用乘数数组 `multipliers` 与 `nums` 数组中的元素相乘的结果。因为每次操作可以选择 `nums` 数组的开头或末尾的元素，所以需要从两个方向进行状态的转移。考虑从开头和末尾选择元素是因为这样可以利用乘数数组中的每个元素与 `nums` 数组中对应位置的元素相乘，确保每个乘数都能用到，从而可能获得最大分数。这种方法确保了每一步选择的灵活性和全面性，是实现最优解的关键。

`dp[j]` 在代码中表示在处理到前 i 个乘数时，从 `nums` 数组的前 j 个元素和后 (i+1-j) 个元素中选择元素所能得到的最大分数。`ndp[j]` 是在下一个乘数处理过程中的临时数组，用于存储更新后的分数值。具体的计算过程是：根据当前的乘数和 `nums` 数组中的元素，更新 `ndp[j]`。如果 j==0，表示只从 `nums` 的末尾选择元素，如果 j 在 1 到 i 之间，可以从 `nums` 的开头或末尾选择元素，如果 j==i+1，表示只从 `nums` 的开头选择元素。通过这样的更新，每一步都尝试所有可能的选择，以便找到可能的最大分数。最后，将 `dp` 更新为 `ndp`，为下一轮计算做准备。