在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