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 크기의 배열 접두사 정의
initialize i :=1의 경우, i <=n일 때 업데이트(i를 1만큼 증가), −
- 접두사[i] :=접두사[i - 1] + 돌[i - 1]
n x n 크기의 2D 배열 dp 하나 정의
길이 초기화:=k의 경우 길이 <=n일 때 업데이트(길이를 1만큼 증가), 수행 -
- initialize i :=0, j :=length - 1, j
- dp[i, j] :=정보
- mid:=i 초기화의 경우 mid
  - 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] + 접두어[j + 1] - 접두어[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