Pythonで乗算演算を実行して最大スコアを見つけるプログラム

それぞれサイズnとmの2つの配列numsと乗数があるとします（n> =m）。配列は1インデックスです。これで、初期スコアは0になります。正確にm個の操作を実行したいと思います。 i番目の操作（1インデックス）では、-

• 数値の最初または最後からxから1つの値を選択します。

• 乗数[i]*xをスコアに追加します。

• 配列番号からxを削除します。

m回の操作を行った後に最大スコアを見つける必要があります。

したがって、入力がnums =[5,10,15]、multipliers =[5,3,2]の場合、15を取り、5を掛けて5 * 15 =75を得ることができるため、出力は115になります。 、次に10 * 3 =30、つまり合計は75 + 30 =105、最後に5 * 2 =10、つまり合計105 + 10=115です。

これを解決するには、次の手順に従います-

• n：=numsのサイズ、m：=サイズ乗数

• dp：=サイズm x（m + 1）の1つの2D配列で、0で塗りつぶします

• iの場合、リスト範囲は0からm-1の逆になります。

  • iからm-1の範囲のjの場合、実行

    • k：=i + m --j --1

    • dp [i、j] =（nums[i]*乗数[k]+dp [i + 1、j]）および（nums [j-m +n]*乗数[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