Minimum Cost to Merge Stones

Similar Problems:

- CheatSheet: Leetcode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #dynamicprogramming, #intervaldp

There are N piles of stones arranged in a row. The i-th 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.

Find 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.

Note:

- 1 <= stones.length <= 30
- 2 <= K <= 30
- 1 <= stones[i] <= 100

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

// https://code.dennyzhang.com/minimum-cost-to-merge-stones // Basic Ideas: DP over interval // dp[i][j] // dp[i][k], dp[k+1][j] // // Complexity: Time O(n^3), Space O(n^2) func min(x, y int) int { if x<y { return x } else { return y } } func mergeStones(stones []int, K int) int { if (len(stones)-1)%(K-1) != 0 { return -1 } dp := make([][]int, len(stones)) for i, _ := range dp { dp[i] = make([]int, len(stones)) } presums := make([]int, len(stones)+1) for i, _ := range stones { presums[i+1] = presums[i]+stones[i] } // dp for i:=len(stones)-1; i>=0; i-- { for j:=i+K-1; j<len(stones); j++ { dp[i][j] = 1<<32-1 for k:=i; k+1<=j; k += K-1 { // dp[i][k], dp[k+1][j] dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]) } if (j-i) % (K-1) == 0 { dp[i][j] += presums[j+1]-presums[i] } } } return dp[0][len(stones)-1] }