Minimum Cost To Merge Stones - Leetcode Solution

The Minimum Cost to Merge Stones problem is a dynamic programming problem on LeetCode. The problem statement is as follows:

You have a list of N stones, where each stone has a certain value. You want to merge the stones together into one pile, but you can only merge adjacent stones. The cost of merging two stones is the sum of their values. Find the minimum cost of merging all the stones into one pile.

To solve this problem, we can use a bottom-up dynamic programming approach. We can define a two-dimensional array dp, where dp[i][j] represents the minimum cost of merging stones i to j into one pile. The base case is when i = j, in which case the cost is 0.

We can then compute the values of dp[i][j] using the following recurrence relation:

dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(a[i..j])), i <= k < j

Here, sum(a[i..j]) represents the sum of values of stones i to j, inclusive. The recurrence relation essentially says that we consider all possible ways of splitting the stones into two sub-piles, merge each sub-pile recursively, and then merge the two resulting piles together at a cost equal to the sum of values of the stones in each pile.

We can compute the values of dp in increasing order of sub-pile sizes. Specifically, we can iterate over all possible sub-pile sizes L, and for each sub-pile size, iterate over all possible starting indices i for sub-piles of that size. For each starting index i, we can compute the corresponding ending index j and then compute the value of dp[i][j] using the recurrence relation.

Finally, the minimum cost of merging all the stones into one pile is given by dp[1][N]. The time complexity of this approach is O(N^3), since there are N^2 possible sub-piles and each sub-pile requires O(N) time to process.

Here's the Python code to implement this approach:

def mergeStones(stones): N = len(stones) dp = [[0] * (N+1) for _ in range(N+1)] for L in range(2, N+1): for i in range(1, N-L+2): j = i + L - 1 dp[i][j] = float('inf') for k in range(i, j): dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum(stones[i-1:j])) return dp[1][N] if dp[1][N] != float('inf') else -1

Note that we initialize dp[i][j] to float('inf') to indicate that the value has not yet been computed. We also check if dp[1][N] is equal to float('inf') after computing all the values, since this indicates that it was not possible to merge all the stones into one pile.

1