Leetcode | Minimum Cost to Merge Stones | Kotlin

devstromo · devstromo · commit ff3602dc5995 · 2025-04-13T15:52:19.000-03:00
diff --git a/leetcode/src/main/kotlin/com/devstromo/hard/p1000/DESCRIPTION.md b/leetcode/src/main/kotlin/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/kotlin/com/devstromo/hard/p1000/SolutionKt.kt b/leetcode/src/main/kotlin/com/devstromo/hard/p1000/SolutionKt.kt
@@ -0,0 +1,39 @@
+package com.devstromo.hard.p1000
+
+class SolutionKt {
+
+    fun mergeStones(stones: IntArray, k: Int): Int {
+        val n = stones.size
+        if ((n - 1) % (k - 1) != 0) return -1
+
+        val prefixSum = IntArray(n + 1)
+        for (i in stones.indices) {
+            prefixSum[i + 1] = prefixSum[i] + stones[i]
+        }
+
+        val dp = Array(n) { Array(n) { IntArray(k + 1) { Int.MAX_VALUE } } }
+
+        for (i in 0 until n) {
+            dp[i][i][1] = 0
+        }
+
+        for (length in 2..n) {
+            for (i in 0..n - length) {
+                val j = i + length - 1
+                for (p in 2..k) {
+                    for (m in i until j step (k - 1)) {
+                        if (dp[i][m][1] != Int.MAX_VALUE && dp[m + 1][j][p - 1] != Int.MAX_VALUE) {
+                            dp[i][j][p] = minOf(dp[i][j][p], dp[i][m][1] + dp[m + 1][j][p - 1])
+                        }
+                    }
+                }
+                // Merge into 1 pile
+                if (dp[i][j][k] != Int.MAX_VALUE) {
+                    dp[i][j][1] = dp[i][j][k] + prefixSum[j + 1] - prefixSum[i]
+                }
+            }
+        }
+
+        return dp[0][n - 1][1]
+    }
+}
diff --git a/leetcode/src/test/kotlin/com/devstromo/hard/p1000/SolutionKtUnitTest.kt b/leetcode/src/test/kotlin/com/devstromo/hard/p1000/SolutionKtUnitTest.kt
@@ -0,0 +1,15 @@
+package com.devstromo.hard.p1000
+
+import org.junit.jupiter.api.Assertions.assertEquals
+import org.junit.jupiter.api.Test
+
+class SolutionKtUnitTest {
+    private val solution = SolutionKt()
+
+    @Test
+    fun `Test Minimum Cost to Merge Stones`() {
+        assertEquals(20, solution.mergeStones(intArrayOf(3, 2, 4, 1), 2))
+        assertEquals(-1, solution.mergeStones(intArrayOf(3, 2, 4, 1), 3))
+        assertEquals(25, solution.mergeStones(intArrayOf(3, 5, 1, 2, 6), 3))
+    }
+}
