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 <= 302 <= K <= 301 <= 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 }