Leetcode | Minimum Cost to Merge Stones | Java

devstromo · devstromo · commit d30f6e992b2b · 2025-04-13T15:48:46.000-03:00
diff --git a/leetcode/src/main/java/com/devstromo/hard/p1000/DESCRIPTION.md b/leetcode/src/main/java/com/devstromo/hard/p1000/DESCRIPTION.md
@@ -0,0 +1,40 @@
+# 1000. Minimum Cost to Merge Stones
+
+There are `n` piles of `stones` arranged in a row. The `ith` 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`.
+
+Example 1:
+
+Input: stones = [3,2,4,1], k = 2
+Output: 20
+Explanation: We start with [3, 2, 4, 1].
+We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
+We merge [4, 1] for a cost of 5, and we are left with [5, 5].
+We merge [5, 5] for a cost of 10, and we are left with [10].
+The total cost was 20, and this is the minimum possible.
+
+Example 2:
+
+Input: stones = [3,2,4,1], k = 3
+Output: -1
+Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore. So the task is impossible.
+
+Example 3:
+
+Input: stones = [3,5,1,2,6], k = 3
+Output: 25
+Explanation: We start with [3, 5, 1, 2, 6].
+We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
+We merge [3, 8, 6] for a cost of 17, and we are left with [17].
+The total cost was 25, and this is the minimum possible.
+
+Constraints:
+
+- `n == stones.length`
+- `1 <= n <= 30`
+- `1 <= stones[i] <= 100`
+- `2 <= k <= 30`
diff --git a/leetcode/src/main/java/com/devstromo/hard/p1000/Solution.java b/leetcode/src/main/java/com/devstromo/hard/p1000/Solution.java
@@ -0,0 +1,33 @@
+package com.devstromo.hard.p1000;
+
+public class Solution {
+    public int mergeStones(int[] stones, int k) {
+        int n = stones.length;
+        if ((n - 1) % (k - 1) != 0) return -1;
+
+        int[][][] dp = new int[n][n][k + 1];
+        int[] prefix = new int[n + 1];
+
+        for (int i = 0; i < n; i++)
+            prefix[i + 1] = prefix[i] + stones[i];
+
+        for (int len = 2; len <= n; len++) {
+            for (int i = 0; i + len <= n; i++) {
+                int j = i + len - 1;
+                for (int p = 2; p <= k; p++) {
+                    dp[i][j][p] = Integer.MAX_VALUE;
+                    for (int m = i; m < j; m += (k - 1)) {
+                        if (dp[i][m][1] == Integer.MAX_VALUE || dp[m + 1][j][p - 1] == Integer.MAX_VALUE)
+                            continue;
+                        dp[i][j][p] = Math.min(dp[i][j][p], dp[i][m][1] + dp[m + 1][j][p - 1]);
+                    }
+                }
+
+                // Merge into 1 pile
+                dp[i][j][1] = (dp[i][j][k] == Integer.MAX_VALUE) ? Integer.MAX_VALUE : dp[i][j][k] + prefix[j + 1] - prefix[i];
+            }
+        }
+
+        return dp[0][n - 1][1];
+    }
+}
diff --git a/leetcode/src/test/java/com/devstromo/hard/p1000/SolutionUnitTest.java b/leetcode/src/test/java/com/devstromo/hard/p1000/SolutionUnitTest.java
@@ -0,0 +1,19 @@
+package com.devstromo.hard.p1000;
+
+import org.junit.jupiter.api.DisplayName;
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class SolutionUnitTest {
+    private final Solution solution = new Solution();
+
+    @Test
+    @DisplayName("Test Minimum Cost to Merge Stones")
+    void testMinimumCostToMergeStones() {
+        assertEquals(20, solution.mergeStones(new int[]{3, 2, 4, 1}, 2));
+        assertEquals(-1, solution.mergeStones(new int[]{3, 2, 4, 1}, 3));
+        assertEquals(25, solution.mergeStones(new int[]{3, 5, 1, 2, 6}, 3));
+    }
+
+}
