用 Python 编写程序，通过执行乘法运算来查找最高得分

pythonserver side programmingprogramming更新于 2025/12/1 2:52:17

假设我们有两个数组 nums 和 multipliers，大小分别为 n 和 m(n >= m)。数组以 1 为索引。现在我们的初始得分为 0。我们想要执行恰好 m 个运算。在第 i 个操作(从 1 开始)中，我们将 −

从数字的开头或结尾处选择一个 x 值。
将 multipliers[i] * x 添加到分数中。
从数组 nums 中删除 x。

我们必须在执行 m 个操作后找到最大分数。

因此，如果输入为 nums = [5,10,15]、multipliers = [5,3,2]，则输出将为 115，因为我们可以取 15，然后将其与 5 相乘得到 5*15 = 75，然后 10*3 = 30，因此总计为 75+30 = 105，最后 5*2 = 10，因此总计 105+10 = 115.

为了解决这个问题，我们将遵循以下步骤 −

n := nums 的大小，m := 大小乘数
dp := 一个大小为 m x (m+1) 的二维数组并用 0 填充
对于 i，反转列表范围 0 到 m - 1，执行
- 对于 j，范围 i 到 m - 1，执行
  - k := i + m - j - 1
  - dp[i, j] = (nums[i] * multipliers[k] + dp[i+1, j]) 和 (nums[j-m+n] * multipliers[k] + dp[i, j-1])
返回 dp[0] 的最后一个元素

示例

让我们看看下面的实现以便更好地理解 −

def solve(nums, multipliers):
   n, m = len(nums), len(multipliers)
   dp = [[0]*m for _ in range(m+1)]

   for i in reversed(range(m)):
      for j in range(i, m):
         k = i + m - j - 1
         dp[i][j] = max(nums[i] * multipliers[k] + dp[i+1][j], nums[j-m+n] * multipliers[k] + dp[i][j-1])

   return dp[0][-1]

nums = [5,10,15]
multipliers = [5,3,2]
print(solve(nums, multipliers))