Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1000.html

1000. Minimum Cost to Merge Stones (Hard)

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

Related Topics:
Dynamic Programming

Similar Questions:

Solution 1. DP

// OJ: https://leetcode.com/problems/minimum-cost-to-merge-stones/
// Time: O(N^3 / K)
// Space: O(N^2)
// Ref: https://leetcode.com/problems/minimum-cost-to-merge-stones/discuss/247567/JavaC%2B%2BPython-DP
class Solution {
public:
    int mergeStones(vector<int>& stones, int K) {
        int N = stones.size();
        if ((N - 1) % (K - 1)) return -1;
        vector<int> prefix(N + 1);
        partial_sum(stones.begin(), stones.end(), prefix.begin() + 1);
        vector<vector<int>> dp(N, vector<int>(N));
        for (int m = K; m <= N; ++m) {
            for (int i = 0; i + m <= N; ++i) {
                int j = i + m - 1;
                dp[i][j] = INT_MAX;
                for (int mid = i; mid < j; mid += K - 1) {
                    dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j]);
                }
                if ((j - i) % (K - 1) == 0) dp[i][j] += prefix[j + 1] - prefix[i];
            }
        }
        return dp[0][N - 1];
    }
};
  • class Solution {
        public int mergeStones(int[] stones, int K) {
            int length = stones.length;
            if (length == 1)
                return 0;
            if ((length - 1) % (K - 1) != 0)
                return -1;
            int[] prefixSum = new int[length];
            prefixSum[0] = stones[0];
            for (int i = 1; i < length; i++)
                prefixSum[i] = prefixSum[i - 1] + stones[i];
            int[][][] dp = new int[length][length][K];
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    for (int k = 0; k < K; k++)
                        dp[i][j][k] = Integer.MAX_VALUE;
                }
            }
            for (int i = 0; i < length; i++)
                dp[i][i][0] = 0;
            for (int curLength = 2; curLength <= length; curLength++) {
                int maxStart = length - curLength;
                for (int i = 0; i <= maxStart; i++) {
                    int end = i + curLength - 1;
                    for (int j = 1; j < K; j++) {
                        for (int k = i; k < end; k += K - 1) {
                            dp[i][end][j] = Math.min(dp[i][end][j], dp[i][k][0] + dp[k + 1][end][j - 1]);
                            dp[i][end][0] = sum(prefixSum, i, end) + dp[i][end][j];
                        }
                    }
                }
            }
            return dp[0][length - 1][0];
        }
    
        public int sum(int[] prefixSum, int start, int end) {
            if (start == 0)
                return prefixSum[end];
            else
                return prefixSum[end] - prefixSum[start - 1];
        }
    }
    
    ############
    
    class Solution {
        public int mergeStones(int[] stones, int K) {
            int n = stones.length;
            if ((n - 1) % (K - 1) != 0) {
                return -1;
            }
            int[] s = new int[n + 1];
            for (int i = 1; i <= n; ++i) {
                s[i] = s[i - 1] + stones[i - 1];
            }
            int[][][] f = new int[n + 1][n + 1][K + 1];
            final int inf = 1 << 20;
            for (int[][] g : f) {
                for(int[] e : g) {
                    Arrays.fill(e, inf);
                }
            }
            for (int i = 1; i <= n; ++i) {
                f[i][i][1] = 0;
            }
            for (int l = 2; l <= n; ++l) {
                for (int i = 1; i + l - 1 <= n; ++i) {
                    int j = i + l - 1;
                    for (int k = 1; k <= K; ++k) {
                        for (int h = i; h < j; ++h) {
                            f[i][j][k] = Math.min(f[i][j][k], f[i][h][1] + f[h + 1][j][k - 1]);
                        }
                    }
                    f[i][j][1] = f[i][j][K] + s[j] - s[i - 1];
                }
            }
            return f[1][n][1];
        }
    }
    
  • // OJ: https://leetcode.com/problems/minimum-cost-to-merge-stones/
    // Time: O(N^3 / K)
    // Space: O(N^2)
    // Ref: https://leetcode.com/problems/minimum-cost-to-merge-stones/discuss/247567/JavaC%2B%2BPython-DP
    class Solution {
    public:
        int mergeStones(vector<int>& stones, int K) {
            int N = stones.size();
            if ((N - 1) % (K - 1)) return -1;
            vector<int> prefix(N + 1);
            partial_sum(stones.begin(), stones.end(), prefix.begin() + 1);
            vector<vector<int>> dp(N, vector<int>(N));
            for (int m = K; m <= N; ++m) {
                for (int i = 0; i + m <= N; ++i) {
                    int j = i + m - 1;
                    dp[i][j] = INT_MAX;
                    for (int mid = i; mid < j; mid += K - 1) {
                        dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j]);
                    }
                    if ((j - i) % (K - 1) == 0) dp[i][j] += prefix[j + 1] - prefix[i];
                }
            }
            return dp[0][N - 1];
        }
    };
    
  • # 1000. Minimum Cost to Merge Stones
    # https://leetcode.com/problems/minimum-cost-to-merge-stones/
    
    class Solution:
        def mergeStones(self, stones: List[int], k: int) -> int:
            n = len(stones)
            if (n - 1) % (k - 1): return -1
            prefix = [0] + list(accumulate(stones))
            
            @cache
            def go(i, j):
                if (j - i + 1) < k: return 0
                
                res = min(go(i, mid) + go(mid + 1, j) for mid in range(i, j, k - 1))
                
                if (j - i) % (k - 1) == 0:
                    res += prefix[j + 1] - prefix[i]
                
                return res
            
            return go(0, n - 1)
    
    
  • func mergeStones(stones []int, K int) int {
    	n := len(stones)
    	if (n-1)%(K-1) != 0 {
    		return -1
    	}
    	s := make([]int, n+1)
    	for i, x := range stones {
    		s[i+1] = s[i] + x
    	}
    	f := make([][][]int, n+1)
    	for i := range f {
    		f[i] = make([][]int, n+1)
    		for j := range f[i] {
    			f[i][j] = make([]int, K+1)
    			for k := range f[i][j] {
    				f[i][j][k] = 1 << 20
    			}
    		}
    	}
    	for i := 1; i <= n; i++ {
    		f[i][i][1] = 0
    	}
    	for l := 2; l <= n; l++ {
    		for i := 1; i <= n-l+1; i++ {
    			j := i + l - 1
    			for k := 2; k <= K; k++ {
    				for h := i; h < j; h++ {
    					f[i][j][k] = min(f[i][j][k], f[i][h][k-1]+f[h+1][j][1])
    				}
    			}
    			f[i][j][1] = f[i][j][K] + s[j] - s[i-1]
    		}
    	}
    	return f[1][n][1]
    }
    
    func min(a, b int) int {
    	if a < b {
    		return a
    	}
    	return b
    }
    

All Problems

All Solutions