leetcode 1000

问题

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:

1
2
3
4
5
6
7
8
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:

1
2
3
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:

1
2
3
4
5
6
7
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

分析

首先可以先来判断一下无效的情况，每次需要合并 K 个连续的石堆成为一个，然后一共是有 N 个石堆，最终要合并成一个。可以分析出每次合并所有石堆的总数量都会减少 K-1 个，最终减少为 1 个，因此一共减少了N-1。所以当 (N-1)%(K-1) == 0 时有解，否则没有解。

思路1: $dp[i][j][k]$ 表示将 $A[i]$~ $A[j]$ 分成 k 堆的最小cost，则有状态转移方程
$$
dp[i][j][k] = min(dp[i][m][1] + dp[m+1][j][k-1]), \; i \leq m < j; \;2 \leq k \leq K
$$

$$
dp[i][j][1] = dp[i][j][K] + sum(A[i]-A[j])
$$

思路2: 优化舍弃状态 k，这个状态并不需要。$dp[i][j]$ 表示 $A[i]$~ $A[j]$ 尽力去合并，合并到 (j-i)%(K-1)+1 个piles，一共所需要的最小花费。则有状态转移方程：
$$
dp[i][j] = min(dp[i][m] + dp[m+1][j]) \;(m = i + Z*(K-1)) \\

  • sum(A[i] - A[j]) \; if ((j-1)\% (K-1)) == 0
    $$
    $O(n^3/K)$

https://www.youtube.com/watch?v=FabkoUzs64o

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 自顶向下 0ms
class Solution {
public:
    int memo[31][31][31];
    vector<int> sum;
    int mergeStones(vector<int>& stones, int K) {
        int n = stones.size();
        memset(memo, -1, sizeof(memo));

        sum = vector<int>(n+1, 0);
        for (int i = 1; i <= n; ++i)
            sum[i] = stones[i-1] + sum[i-1];

        if ((n-1)%(K-1)) return -1;
        return dp(stones, 0, n-1, 1, K);
    }

    int dp(vector<int> &stones, int i, int j, int k, int K) {
        if (memo[i][j][k] >= 0)
            return memo[i][j][k];
        int ret = INT_MAX/2;
        if (k == 1) {
            int len = j-i+1;
            if (len == 1) return memo[i][j][k] = 0;
            if (len < K)  return memo[i][j][k] = ret;
            if (len == K) {
                return memo[i][j][k] = sum[j+1]-sum[i];
            }
            return memo[i][j][k] = dp(stones, i, j, K, K) + sum[j+1]-sum[i];
        }

        // spile point z
        for (int z = i; z < j; z += K-1) {
            ret = min(ret, dp(stones, i, z, 1, K) + dp(stones, z+1, j, k-1, K));
        }

        return memo[i][j][k] = ret;
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 自底向上  20ms
class Solution {
public:
    int mergeStones(vector<int>& stones, int K) {
        int n = stones.size();
        const int kInf = 0x3f3f3f3f;
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(K+1, kInf)));
        vector<int> sum(n+1, 0);
        for (int i = 1; i <= n; ++i) sum[i] = sum[i-1] + stones[i-1];
        if ((n-1)%(K-1))
            return -1;
        
        for (int i = 0; i < n; ++i) dp[i][i][1] = 0;

        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i< n-len+1; ++i) {
                int j = i+len-1;
                for (int k = 2; k <= K; ++k) {
                    for (int z = i; z < j; z += K-1) {
                        dp[i][j][k] = min(dp[i][j][k], dp[i][z][1] + dp[z+1][j][k-1]);
                    }
                }
                if (dp[i][j][K] < kInf) {
                    dp[i][j][1] = dp[i][j][K] + sum[j+1] - sum[i];
                }
            }
        }
        return dp[0][n-1][1];
    }
};

代码3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 0ms
class Solution {
public:
    int mergeStones(vector<int>& stones, int K) {
        int n = stones.size();
        const int kInf = 0x3f3f3f3f;
        vector<vector<int>>dp (n, vector<int>(n, kInf));
        vector<int> sum(n+1, 0);
        for (int i = 1; i <= n; ++i) sum[i] = sum[i-1] + stones[i-1];

        if ((n-1)%(K-1))
            return -1;

        for (int i = 0; i < n; ++i) dp[i][i] = 0;

        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i< n-len+1; ++i) {
                int j = i+len-1;
                for (int z = i; z < j; z += K-1) {
                    dp[i][j] = min(dp[i][j], dp[i][z]+dp[z+1][j]);
                }
                if (((j-i)%(K-1)) == 0)
                    dp[i][j] += sum[j+1]-sum[i];
            }
        }
        return dp[0][n-1];
    }
};