資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中合併石頭的最小成本
假設我們有一排 N 堆石頭。這裡第 i 堆有 stones[i] 個石頭。一次移動包括將 K 個連續的堆合併成一堆，現在這次移動的成本等於這 K 個堆中石頭的總數。我們必須找到將所有石堆合併成一堆的最小成本。如果沒有這樣的解決方案，則返回 -1。
因此，如果輸入類似於 [3,2,4,1] 且 K = 2，則輸出將為 20，這是因為，我們將從 [3, 2, 4, 1] 開始。然後我們將 [3, 2] 合併，成本為 5，我們剩下 [5, 4, 1]。之後我們合併 [4, 1]，成本為 5，我們剩下 [5, 5]。然後我們將 [5, 5] 合併，成本為 10，我們剩下 [10]。所以，總成本為 20，這是最小的。
為了解決這個問題，我們將遵循以下步驟：
n := stones 的大小
如果 (n - 1) mod (k - 1) 不等於 0，則：
返回 -1
定義一個大小為 n + 1 的陣列 prefix
初始化 i := 1，當 i <= n 時，更新（i 增加 1），執行：
prefix[i] := prefix[i - 1] + stones[i - 1]
定義一個大小為 n x n 的二維陣列 dp
初始化 length := k，當 length <= n 時，更新（length 增加 1），執行：
初始化 i := 0，j := length - 1，當 j < n 時，更新（i 增加 1），（j 增加 1），執行：
dp[i, j] := inf
初始化 mid := i，當 mid < j 時，更新 mid := mid + k - 1，執行：
dp[i, j] := dp[i, j] 和 dp[i, mid] + dp[mid + 1, j] 的最小值
如果 (j - i) mod (k - 1) 與 0 相同，則：
dp[i, j] := dp[i, j] + prefix[j + 1] - prefix[i]
返回 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
537 次瀏覽
