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

更新於: 2021年10月6日

258 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告