Pythonで石をマージするための最小コストを見つけるためのプログラム

N個の石の山が一列に並んでいると仮定します。ここで、i番目の山には石[i]個の石があります。移動は、K個の連続する杭を1つの杭にマージすることで構成されます。この移動のコストは、これらのK個の杭の石の総数に等しくなります。石のすべての山を1つの山にマージするための最小コストを見つける必要があります。そのような解決策がない場合は、-1を返します。

したがって、入力がnums =[3,2,4,1]、K =2のような場合、最初は[3、2、4、1]であるため、出力は20になります。次に、[3、2]をコスト5とマージすると、[5、4、1]が得られます。その後、[4、1]をコスト5とマージし、[5、5]を作成します。次に、[5、5]をコスト10とマージすると、[10]が得られます。つまり、総コストは20で、これが最小のコストです。

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

• n：=numsのサイズ

• （n-1）mod（K-1）が0でない場合、

  • -1を返す

• dp：=1つのnxn配列と0で埋める

• 合計：=nサイズの配列（n + 1）および0で埋める

• 1からnの範囲のiの場合、実行します

  • sums [i]：=sums [i-1] + nums [i-1]

• Kからnの範囲の長さについては、実行してください

  • 0からnの長さの範囲のiの場合、実行します

    • j：=i + length-1

    • dp [i、j]：=無限大

    • iからj-1の範囲のtについては、各ステップでK-1ずつ更新します。

      • dp [i] [j]=最小のdp[i、j]および（dp [i、t] + dp [t + 1、j]）

    • （j-i）mod（K-1）が0と同じ場合、

      • dp [i、j]：=dp [i、j] + sums [j + 1]-sums [i]

• dp [0、n-1]

  を返します

例

理解を深めるために、次の実装を見てみましょう

import heapq
def solve(nums, K):
   n = len(nums)
   if (n-1)%(K-1) != 0:
      return -1
   dp = [[0]*n for _ in range(n)]
   sums = [0]*(n+1)
   for i in range(1,n+1):
      sums[i] = sums[i-1]+nums[i-1]
   for length in range(K,n+1):
      for i in range(n-length+1):
         j = i+length-1
         dp[i][j] = float('inf')
         for t in range(i,j,K-1):
            dp[i][j] = min(dp[i][j], dp[i][t]+dp[t+1][j])
         if (j-i)%(K-1)==0:
            dp[i][j] += sums[j+1]-sums[i]
   return dp[0][n-1]

nums = [3,2,4,1]
K = 2
print(solve(nums, K))

入力

[3,2,4,1], 2

出力

20