LeetCode: Minimum Cost to Merge Stones

Minimum Cost to Merge Stones

Similar Problems:

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

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]
}