aboutsummaryrefslogtreecommitdiff
path: root/min_cost_merge_stones.py
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 /min_cost_merge_stones.py
parent1539df1b1354faff30151ccaa907793b362b27d5 (diff)
downloadleetcode-c52e6aefdc74847dff8ac39dd89b5253b375f524.tar.gz
leetcode-c52e6aefdc74847dff8ac39dd89b5253b375f524.zip
1000. minimum cost to merge stones
Diffstat (limited to 'min_cost_merge_stones.py')
-rw-r--r--min_cost_merge_stones.py43
1 files changed, 43 insertions, 0 deletions
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))