1000. Minimum Cost to Merge Stones
There are
N
piles of stones arranged in a row. Thei
-th pile hasstones[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 theseK
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
Approach #1: DP. [C++]
class Solution { public: int mergeStones(vector<int>& stones, int K) { int n = stones.size(); if ((n-1) % (K-1)) return -1; const int kInf = 1e9 + 7; vector<int> sum(n+1, 0); for (int i = 0; i < n; ++i) sum[i+1] = sum[i] + stones[i]; vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(n+1, vector<int>(K+1, kInf))); for (int i = 0; i < n; ++i) dp[i][i][1] = 0; for (int l = 2; l <= n; ++l) { for (int i = 0; i <= n - l; ++i) { int j = i + l - 1; for (int k = 2; k <= K; ++k) { for (int m = i; m < j; ++m) { dp[i][j][k] = min(dp[i][j][k], dp[i][m][1] + dp[m+1][j][k-1]); } } dp[i][j][1] = dp[i][j][K] + sum[j+1] - sum[i]; } } return dp[0][n-1][1]; } };
Analysis:
Non-overlapping subproblems: min cost of merging subarray A[i]~A[j] into k piles.
dp[i][j][k] : min cost to merge A[i]~A[j] into k piles
Init: dp[i][i][1] = 0 : no cost to merge one into one
Transition:
1. dp[i][j][k] = min(dp[i][m][1] + dp[i][m+1][k-1]}, i <= m < j, 2 <= k <= K
2. dp[i][j][1] = dp[i][j][K] + sum(A[i] ~ A[j])
ans : dp[0][n-1][1] # merge he whole array into one.
Approach #2: DP + Optimization. [Java]
class Solution { public int mergeStones(int[] stones, int K) { int n = stones.length; if ((n-1) % (K-1) != 0) return -1; int[] prefix = new int[n+1]; for (int i = 0; i < n; ++i) prefix[i+1] = prefix[i] + stones[i]; int[][] dp = new int[n][n]; for (int l = 2; l <= n; ++l) { for (int i = 0; i <= n-l; ++i) { int j = i + l - 1; dp[i][j] = Integer.MAX_VALUE; for (int m = i; m < j; m += K - 1) dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m+1][j]); if ((j-i) % (K-1) == 0) dp[i][j] += prefix[j+1] - prefix[i]; } } return dp[0][n-1]; } }
Analysis:
Optimization 1: In order to merge left part into 1 pile, (len - 1) % (K - 1) == 0
++m => m += K-1;
Optimization 2: The number of piles the right part can be merge into can be determined, (len - 1) % (K - 1) + 1. And we need to merge them first before the final merge of left and right.
dp[i][j] : min cost to merge A[i] ~ A[j] to (j-i) % (K-1) + 1 piles
Init: dp[i][i] = 0
dp[i][j] = min(dp[i][m] + dp[m+1][j]} + sum(A[i] ~ A[j]) if (j - i) % (K - 1) == 0
Reference:
https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-1000-minimum-cost-to-merge-stones/
https://leetcode.com/problems/minimum-cost-to-merge-stones/discuss/247567/JavaC%2B%2BPython-DP
相关文章
- [Tools] Using Webpack require.context to conditionally load file
- [Recompose] Merge RxJS Button Event Streams to Build a React Counter Component
- [RxJS] Use RxJS mergeMap to map and merge high order observables
- [CSS] Introduction to CSS Columns
- my Note debug - add to function
- association in CDS view is converted to LEFT OUTER MANY TO ONE JOIN in the runtime
- how to find all element type with type table of content
- how to avoid transport error when cloning project in Eclipse
- 成功解决To fix this you could try to: 1. loosen the range of package versions you‘ve specified
- 已解决 A possible replacement is to enable the ‘–use-pep517’ option. Discussion can be found at https:/
- Introduction to nonlinear optimization第四章习题
- refusing to merge unrelated histories的解决方案(git 本地/远程仓库合并)
- 【错误记录】Android Studio 中编写 Gradle 编译脚本时没有 Groovy 代码提示 ( Cannot find declaration to go to )
- PAT 1033 To Fill or Not to Fill[dp]
- redis.clients.jedis.exceptions.JedisException: Can connect to sentinel, but seems to be not monitored.
- 记Git报错-refusing to merge unrelated histories
- [Git & GitHub] 解决办法:Can’t connect to any repository : not authorized / not permitted