Chi phí nhỏ nhất để gộp đá trong C++

Cho N đống đá xếp hàng ngang, đống i có stones[i] viên. Mỗi lần gộp K đống liên tiếp thành một đống, chi phí bằng tổng số viên đá trong K đống đó. Tìm chi phí nhỏ nhất để gộp tất cả thành một đống. Nếu không thể, trả về -1.

Ví dụ: [3,2,4,1], K=2 → chi phí 20.

Giải thuật

1. Nếu (n-1) % (K-1) != 0 thì trả về -1 (không thể gộp về 1 đống).
2. Tính mảng tiền tố prefix để truy vấn tổng đoạn O(1).
3. DP quy hoạch động: dp[i][j] = chi phí nhỏ nhất gộp đoạn [i..j] thành số đống hợp lệ.
4. Duyệt độ dài từ K đến n:
   • Với mỗi đoạn [i, j], khởi tạo dp[i][j] = INF.
   • Thử tách tại mid (bước nhảy K-1): dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid+1][j]).
   • Nếu (j-i) % (K-1) == 0, có thể gộp thành 1 đống: dp[i][j] += prefix[j+1] - prefix[i].
5. Trả về dp[0][n-1].

Ví dụ mã C++

#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 len = k; len <= n; len++) {
            for (int i = 0, j = len-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];
    }
};
int main(){
    Solution ob;
    vector<int> v = {3,2,4,1};
    cout << (ob.mergeStones(v, 2));
}

Đầu vào

{3,2,4,1}, 2

Đầu ra

20