Minimum Cost to Merge Stones - Solution & Explanation

Problem Overview: You are given an array of stone piles and an integer k. Each move merges exactly k consecutive piles into one pile, costing the total number of stones in those piles. The goal is to minimize the total merge cost required to combine all piles into a single pile. If it is impossible due to the merge constraint, return -1.

Approach 1: Brute Force Recursive Partitioning (Exponential Time, O(n) space)

The most direct idea tries every valid way to merge k consecutive piles. For each interval, recursively compute the cost of merging left and right partitions, then add the sum of stones when the interval becomes one pile. This approach repeatedly recomputes the same subproblems and explores all possible partitions. Time complexity becomes exponential because each interval branches into multiple merge choices. Space complexity is O(n) for the recursion stack. This method mainly helps you understand the structure of the problem before applying optimization.

Approach 2: Top‑Down Dynamic Programming with Memoization (O(n^3) time, O(n^2) space)

Memoization avoids recomputing subproblems. Define dp(i, j) as the minimum cost to merge piles from index i to j. Only partitions that maintain the ability to merge into valid pile counts are explored. The recursion splits the range at valid positions and stores results in a memo table. To compute the merge cost quickly, use a prefix sum array so the total stones in any interval can be retrieved in O(1). This reduces the brute force explosion but still checks many interval partitions, giving O(n^3) time and O(n^2) space.

Approach 3: Bottom‑Up Dynamic Programming with Prefix Sums (O(n^3) time, O(n^2) space)

The standard optimal solution builds results for increasing interval lengths. Let dp[i][j] represent the minimum cost to merge piles between indices i and j. Iterate over interval lengths and try splitting the segment into two smaller intervals. Because merges only occur in groups of k, partitions advance by k‑1 steps to maintain valid pile counts. A prefix sum array lets you compute the total stones of an interval instantly when a final merge is possible. The algorithm iterates over start index, end index, and partition point, resulting in O(n^3) time and O(n^2) space. This method combines interval dynamic programming with efficient range sum queries on the array.

Recommended for interviews: The bottom‑up DP with prefix sums is the expected solution. Interviewers want to see interval DP reasoning: defining subproblems on ranges, enforcing the k-merge constraint, and using prefix sums to avoid repeated range summations. Starting from the brute force idea and then introducing memoization shows problem‑solving progression, but implementing the optimized DP demonstrates strong algorithmic maturity.