LeetCode 1000: Minimum Cost to Merge Stones Solution

Master LeetCode problem 1000 (Minimum Cost to Merge Stones), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1000. Minimum Cost to Merge Stones

Hard

Array Dynamic Programming Prefix Sum

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We define a 3D dp array where dp[i][j][m] represents the minimum cost to merge stones from piles i to j (inclusive) into m piles. We can then iterate over the array to fill in the values based on the subproblems.

Initialize the dp array with size n x n x k.
Perform a bottom-up dynamic programming approach to fill in the dp array.
Return the result stored at dp[0][n-1][1] if possible, else return -1.

Time complexity: O(n^3) Space complexity: O(n^2)

Solution Code

class Solution {
    public int mergeStones(int[] stones, int k) {
        int n = stones.length;
        if ((n - 1) % (k - 1) != 0) {
            return -1;
        }
        
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stones[i];
        }
        
        int[][][] dp = new int[n][n][k + 1];
        
        for (int len = k; len <= n; len++) {
            for (int i = 0; i + len <= n; i++) {
                int j = i + len - 1;
                for (int m = 1; m <= k; m++) {
                    dp[i][j][m] = Integer.MAX_VALUE;
                    for (int mid = i; mid < j; mid += k - 1) {
                        dp[i][j][m] = Math.min(dp[i][j][m], dp[i][mid][1] + dp[mid + 1][j][m - 1]);
                    }
                    if ((j - i) % (k - 1) == 0) {
                        dp[i][j][1] = dp[i][j][m] + prefixSum[j + 1] - prefixSum[i];
                    }
                }
            }
        }
        
        return dp[0][n - 1][1];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1000 (Minimum Cost to Merge Stones)?

This page provides optimized solutions for LeetCode problem 1000 (Minimum Cost to Merge Stones) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1000 (Minimum Cost to Merge Stones)?

The time complexity for LeetCode 1000 (Minimum Cost to Merge Stones) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1000 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1000 in Java, C++, or Python.

Back to LeetCode Solutions