# Участник:Novruzov.sb/Minimum Cost to Merge Stones

Перейти к: навигация, поиск

C++

```class Solution {
public:
bool incr_partition(int part[], int size, int step, int end) {
if (end < 1) {
return false;
}
part[size-1] += step;
if (part[size-1] >= end) {
if (size == 1) {
return false;
}
bool ret = incr_partition(part, size-1, step, end-1);
if (ret) {
part[size-1] = part[size-2] + 1;
}
return ret;
}
return true;
}

int mergeStones(vector<int>& stones, int K) {
int N = stones.size();
if (K != 2 and N % (K-1) != 1) {
return -1;
}
int memo[N+1][N+1];
for (int i = 0; i < N; i++) {
memo[i][i+1] = 0;
}
int subsize = K;
int end;
int partitions[K-1];
bool cont;
int min_cost, cost;
int max_cost = 1000000;
while (subsize <= N) {
for(int i = 0; i < N - subsize + 1; ++i) {
end = i + subsize;
for (int j = 0; j < K-1; j++) {
partitions[j] = i+j+1;
}
cont = true;
min_cost = max_cost;
while (cont) {
cost = memo[i][partitions[0]] + memo[partitions[K-2]][end];
for (int j = 0; j < K-2; j++) {
cost += memo[partitions[j]][partitions[j+1]];
}
for (int j = i; j < end; j++) {
cost += stones[j];
}
if (cost < min_cost) {
min_cost = cost;
}
cont = incr_partition(partitions, K-1, K-1, end);
}
memo[i][end] = min_cost;
}
subsize += K-1;
}
return memo[0][N];
}
};
```