在C ++中合并石头的最低成本

假设我们有N排石头排成一排。在这里，第i堆有石头[i]数。一次移动包括将K个连续的桩合并为一个桩，现在此移动的成本等于这K个桩中的石头总数。我们必须找到将所有石头堆成一堆的最低成本。如果没有这样的解决方案，则返回-1。

因此，如果输入像[3,2,4,1]且K = 2，则输出将为20，这是因为我们将从[3，2，4，1]开始。然后我们以成本5合并[3，2]，剩下[5，4，1]。之后，我们以5的成本合并[4，1]，然后剩下[5，5]。然后我们以成本10合并[5，5]，剩下[10]。因此，总成本为20，这是最低的成本。

为了解决这个问题，我们将遵循以下步骤-

• n：=石头大小

• 如果(n-1)mod(k-1)不等于0，则-

• 返回-1

• 定义大小为n + 1的数组前缀

• 对于初始化i：= 1，当i <= n时，更新（将i增加1），-

• prefix [i]：=前缀[i-1] +石头[i-1]

• 定义一个大小为nxn的2D数组dp

• 对于初始化长度：= k，当长度<= n时，更新（将长度增加1），-

• dp [i，j]：= dp [i，j] +前缀[j + 1]-前缀[i]

• dp [i，j]：= dp [i，j]和dp [i，mid]的最小值+ dp [mid + 1，j]

• 对于初始化i：= 0，j：=长度-1，当j <n时，更新（i增加1），（j增加1），-

• dp [i，j]：= inf

• 对于初始化mid：= i，当mid <j时，更新mid：= mid + k-1，执行-

• 如果(j-i)mod(k-1)等于0，则-

• 返回dp [0，n-1]

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int mergeStones(vector<int>& stones, int k){
      int n = stones.size();
      if ((n - 1) % (k - 1) != 0)
      return -1;
      vector<int> prefix(n + 1);
      for (int i = 1; i <= n; i++) {
         prefix[i] = prefix[i - 1] + stones[i - 1];
      }  
      vector<vector<int>> dp(n, vector<int>(n));
      for (int length = k; length <= n; length++) {
         for (int i = 0, j = length - 1; j < n; i++, j++) {
            dp[i][j] = INT_MAX;
            for (int mid = i; mid < j; mid += k - 1) {
               dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid +
               1][j]);
            }
            if ((j - i) % (k - 1) == 0) {
               dp[i][j] += prefix[j + 1] - prefix[i];
            }
         }
      }
      return dp[0][n - 1];
   }
};
main(){
   Solution ob;
   vector<int> v = {3,2,4,1};
   cout << (ob.mergeStones(v, 2));
}

输入值

{3,2,4,1}, 2

输出结果

20