Chi phí tối thiểu để hợp nhất các viên đá trong C ++

Giả sử chúng ta có N đống đá xếp thành một hàng. Ở đây đống thứ i có đá [i] số đá. Một nước đi bao gồm gộp K cọc liên tiếp thành một cọc, bây giờ chi phí của lần di chuyển này bằng tổng số đá trong K số cọc này. Chúng ta phải tìm chi phí tối thiểu để ghép tất cả các đống đá thành một đống. Nếu không có giải pháp nào như vậy, hãy trả về -1.

Vì vậy, nếu đầu vào là [3,2,4,1] và K =2, thì đầu ra sẽ là 20, điều này là do, chúng ta sẽ bắt đầu với [3, 2, 4, 1]. Sau đó, chúng tôi hợp nhất [3, 2] với chi phí là 5, và chúng tôi còn lại với [5, 4, 1]. Sau đó, chúng tôi hợp nhất [4, 1] với chi phí là 5, và chúng tôi còn lại với [5, 5]. Sau đó, chúng tôi hợp nhất [5, 5] với chi phí là 10, và chúng tôi còn lại với [10]. Vì vậy, tổng chi phí là 20 và đây là chi phí tối thiểu.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của đá

• nếu (n - 1) mod (k - 1) không bằng 0, thì -

  • trả về -1

• Xác định tiền tố mảng có kích thước n + 1

• để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), thực hiện -

  • prefix [i]:=prefix [i - 1] + stone [i - 1]

• Xác định một dp mảng 2D có kích thước n x n

• để khởi tạo độ dài:=k, khi độ dài <=n, cập nhật (tăng độ dài thêm 1), thực hiện -

  • để khởi tạo i:=0, j:=length - 1, khi j

  • dp [i, j]:=inf

  • để khởi tạo mid:=i, khi mid

    • dp [i, j]:=tối thiểu của dp [i, j] và dp [i, mid] + dp [mid + 1, j]

  • nếu (j - i) mod (k - 1) giống 0, thì -

    • dp [i, j]:=dp [i, j] + prefix [j + 1] - prefix [i]

• trả về dp [0, n - 1]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

{3,2,4,1}, 2

Đầu ra

20