aboutsummaryrefslogtreecommitdiff
path: root/min_cost_merge_stones.c
diff options
context:
space:
mode:
Diffstat (limited to 'min_cost_merge_stones.c')
-rw-r--r--min_cost_merge_stones.c49
1 files changed, 49 insertions, 0 deletions
diff --git a/min_cost_merge_stones.c b/min_cost_merge_stones.c
new file mode 100644
index 0000000..000aa6f
--- /dev/null
+++ b/min_cost_merge_stones.c
@@ -0,0 +1,49 @@
+// 1000. Minimum Cost to Merge Stones
+#include "leetcode.h"
+
+/*
+ * there are 'n' piles of 'stones' arrange in a row. the i'th pile has
+ * 'stones[i]' stones. a move consists of merging exactly 'k' consecutive piles
+ * into one pile and the cost of this move is equal to the total number of
+ * stones in these 'k' piles. return the minimum cost to merge all piles of
+ * stones into one pile. if it is impossible, return -1
+ */
+
+#define MAX_CNT 20
+
+int mergeStones(int *stones, int stonesSize, int k) {
+ if ((stonesSize - 1) % (k - 1))
+ return -1;
+ int sum = 0, dp[MAX_CNT][MAX_CNT] = {0}, sum_arr[MAX_CNT + 1] = {0};
+ for (int i = 0; i < stonesSize; i++)
+ sum = sum_arr[i] = sum + stones[i];
+ for (int i = 0; i < stonesSize; i++) {
+ int j = i + k - 1;
+ if (j < stonesSize) {
+ dp[i][j] = sum_arr[j];
+ if (i)
+ dp[i][j] -= sum_arr[i - 1];
+ }
+ }
+ for (int i = 0; i < stonesSize - k; i++)
+ for (int j = 0, n = k + i; n < stonesSize; j++, n++) {
+ dp[j][n] = INT_MAX;
+ for (int mid = j; mid < n; mid += (k - 1)) {
+ int res = dp[j][mid] + dp[mid + 1][n];
+ dp[j][n] = res < dp[j][n] ? res : dp[j][n];
+ }
+ if (!((n - j) % (k - 1))) {
+ dp[j][n] += sum_arr[j];
+ if (j)
+ dp[j][n] -= sum_arr[j - 1];
+ }
+ }
+ return dp[0][stonesSize - 1];
+}
+
+int main() {
+ int s1[] = {3, 2, 4, 1}, s2[] = {3, 2, 4, 1}, s3[] = {3, 5, 1, 2, 6};
+ printf("%d\n", mergeStones(s1, ARRAY_SIZE(s1), 2)); // expect: 20
+ printf("%d\n", mergeStones(s2, ARRAY_SIZE(s2), 3)); // expect: -1
+ printf("%d\n", mergeStones(s3, ARRAY_SIZE(s3), 3)); // expect: 25
+}