diff options
author | Jack Sangdahl <[email protected]> | 2024-09-09 14:27:22 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-09-09 14:27:22 -0600 |
commit | c52e6aefdc74847dff8ac39dd89b5253b375f524 (patch) | |
tree | d39abcc38cd895f79ac7044ae93a512d233f9cc1 | |
parent | 1539df1b1354faff30151ccaa907793b362b27d5 (diff) | |
download | leetcode-c52e6aefdc74847dff8ac39dd89b5253b375f524.tar.gz leetcode-c52e6aefdc74847dff8ac39dd89b5253b375f524.zip |
1000. minimum cost to merge stones
-rw-r--r-- | min_cost_merge_stones.c | 49 | ||||
-rw-r--r-- | min_cost_merge_stones.py | 43 |
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)) |