Python程序：查找执行乘法运算后的最大得分

假设我们有两个数组 nums 和 multipliers，大小分别为 n 和 m（n >= m）。数组从 1 开始索引。现在我们的初始得分为 0。我们想要执行正好 m 次操作。在第 i 次操作（从 1 开始索引）中，我们将：

• 从 nums 的开头或结尾选择一个值 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 := multipliers 的大小

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

输入

[5,10,15], [5,3,2]

输出

115

Arnab Chakraborty

更新于: 2021年10月6日

258 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习