aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-09 14:27:22 -0600
committerJack Sangdahl <[email protected]>2024-09-09 14:27:22 -0600
commitc52e6aefdc74847dff8ac39dd89b5253b375f524 (patch)
treed39abcc38cd895f79ac7044ae93a512d233f9cc1
parent1539df1b1354faff30151ccaa907793b362b27d5 (diff)
downloadleetcode-c52e6aefdc74847dff8ac39dd89b5253b375f524.tar.gz
leetcode-c52e6aefdc74847dff8ac39dd89b5253b375f524.zip
1000. minimum cost to merge stones
-rw-r--r--min_cost_merge_stones.c49
-rw-r--r--min_cost_merge_stones.py43
2 files changed, 92 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
+}
diff --git a/min_cost_merge_stones.py b/min_cost_merge_stones.py
new file mode 100644
index 0000000..019bbdf
--- /dev/null
+++ b/min_cost_merge_stones.py
@@ -0,0 +1,43 @@
+# 1000. Minimum Cost to Merge Stones
+from functools import lru_cache
+
+"""
+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
+"""
+
+
+class Solution(object):
+ def mergeStones(self, stones, k):
+ """
+ :type stones: List[int]
+ :type k: int
+ :rtype: int
+ """
+ n = len(stones)
+ if (n - 1) % (k - 1):
+ return -1
+ prefix = [0] * (n + 1)
+ for i in range(n):
+ prefix[i + 1] = prefix[i] + stones[i]
+
+ @lru_cache(None)
+ def dp(i, j):
+ if j - i + 1 < k:
+ return 0
+ ans = min(dp(i, mid) + dp(mid + 1, j) for mid in range(i, j, k - 1))
+ if (j - i) % (k - 1) == 0:
+ ans += prefix[j + 1] - prefix[i]
+ return ans
+
+ return dp(0, n - 1)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.mergeStones(stones=[3, 2, 4, 1], k=2))
+ print(obj.mergeStones(stones=[3, 2, 4, 1], k=3))
+ print(obj.mergeStones(stones=[3, 5, 1, 2, 6], k=3))