Leetcode | Minimum Cost to Merge Stones | Kotlin

devstromo · devstromo · commit c2d85d379c7c · 2025-04-13T15:53:18.000-03:00
diff --git a/leetcode/src/main/kotlin/com/devstromo/hard/p1000/SolutionKt.kt b/leetcode/src/main/kotlin/com/devstromo/hard/p1000/SolutionKt.kt
@@ -36,4 +36,31 @@ class SolutionKt {
 
         return dp[0][n - 1][1]
     }
+
+    fun mergeStonesBest(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 0 until n) {
+            prefixSum[i + 1] = prefixSum[i] + stones[i]
+        }
+
+        val dp = Array(n) { IntArray(n) }
+        for (length in k..n) {
+            for (i in 0..n - length) {
+                val j = i + length - 1
+                dp[i][j] = Int.MAX_VALUE
+                for (m in i until j step k - 1) {
+                    dp[i][j] = minOf(dp[i][j], dp[i][m] + dp[m + 1][j])
+                }
+                if ((j - i) % (k - 1) == 0) {
+                    dp[i][j] += prefixSum[j + 1] - prefixSum[i]
+                }
+            }
+        }
+        return dp[0][n - 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
@@ -12,4 +12,11 @@ class SolutionKtUnitTest {
         assertEquals(-1, solution.mergeStones(intArrayOf(3, 2, 4, 1), 3))
         assertEquals(25, solution.mergeStones(intArrayOf(3, 5, 1, 2, 6), 3))
     }
+
+    @Test
+    fun `Test Minimum Cost to Merge Stones Best`() {
+        assertEquals(20, solution.mergeStonesBest(intArrayOf(3, 2, 4, 1), 2))
+        assertEquals(-1, solution.mergeStonesBest(intArrayOf(3, 2, 4, 1), 3))
+        assertEquals(25, solution.mergeStonesBest(intArrayOf(3, 5, 1, 2, 6), 3))
+    }
 }

Original file line number	Diff line number	Diff line change
`@@ -12,4 +12,11 @@ class SolutionKtUnitTest {`
`12`	`12`	`assertEquals(-1, solution.mergeStones(intArrayOf(3, 2, 4, 1), 3))`
`13`	`13`	`assertEquals(25, solution.mergeStones(intArrayOf(3, 5, 1, 2, 6), 3))`
`14`	`14`	`}`
	`15`	`+`
	`16`	`+ @Test`
	`17`	+ fun `Test Minimum Cost to Merge Stones Best`() {
	`18`	`+ assertEquals(20, solution.mergeStonesBest(intArrayOf(3, 2, 4, 1), 2))`
	`19`	`+ assertEquals(-1, solution.mergeStonesBest(intArrayOf(3, 2, 4, 1), 3))`
	`20`	`+ assertEquals(25, solution.mergeStonesBest(intArrayOf(3, 5, 1, 2, 6), 3))`
	`21`	`+ }`
`15`	`22`	`}`