在Python中查找执行乘法操作的最高分数的程序

假设我们有大小分别为n和m（n≥m）的两个nums和multipliers数组。数组是以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）的2D数组，并用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))