# [LeetCode] Minimum Cost to Merge Stones 混合石子的最小花费

2022年11月23日
0 收藏 653 点赞 4,466 浏览 3709 个字

There are `N` piles of stones arranged in a row.  The `i`-th pile has `stones[i]` stones.

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 = 2Output: 20Explanation: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 = 3Output: -1Explanation: 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 = 3Output: 25Explanation: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`

`dp[i][j] = min(dp[i][j], dp[i][t] + dp[t + 1][j]); -> (i <= t < j)`

`dp[i][j] += sums[j + 1] - sums[i]; -> if ((j - i) % (K - 1) == 0)`

``class Solution {public:    int mergeStones(vector<int>& stones, int K) {    int n = stones.size();    if ((n - 1) % (K - 1) != 0) return -1;        vector<int> sums(n + 1);        vector<vector<int>> dp(n, vector<int>(n));        for (int i = 1; i < n + 1; ++i) {            sums[i] = sums[i - 1] + stones[i - 1];        }        for (int len = K; len <= n; ++len) {            for (int i = 0; i + len <= n; ++i) {            int j = i + len - 1;            dp[i][j] = INT_MAX;                for (int t = i; t < j; t += K - 1) {                    dp[i][j] = min(dp[i][j], dp[i][t] + dp[t + 1][j]);                }                if ((j - i) % (K - 1) == 0) {                dp[i][j] += sums[j + 1] - sums[i];                }            }        }        return dp[0][n - 1];    }};``

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1000

Burst Balloons

Remove Boxes

Cherry Pickup

https://leetcode.com/problems/minimum-cost-to-merge-stones/

https://leetcode.com/problems/minimum-cost-to-merge-stones/discuss/247567/JavaC%2B%2BPython-DP

LeetCode All in One 题目讲解汇总(持续更新中…)

python开发_常用的python模块及安装方法

Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…

zengkefu@server1:/usr/src\$ uname -aLinux server1 4.10.0-19-generic #21…

Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…

Struts的使用

400-888-8888

ceotheme@ceo.com