LeetCode/Minimum Cost to Merge Stones

Problem Summary

There are N piles of stones in a row. The i-th pile has Xi 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 impossible, return -1.

1 ≤ N ≤ 30
2 ≤ K ≤ 30
1 ≤ Xi ≤ 100

Analysis

First of all, if we carry out a merge on N stones, it will become N-(K-1) piles. If we carry out as many times of merge as possible, there will be (N-1) % (K-1) + 1 piles left.

So, if and only if (N-1) % (K-1) = 0, it is possible to merge N piles into 1 pile.

Solution 1

Now assume we have (N-1) % (K-1) = 0. We can solve this with dynamic programming. Let f[i][j][t] be the minimum cost of merging [Xi, Xi+1, …, Xj] into t piles.

1. If t = 1, f[i][j][t] = f[i][j][K] + Xi + … + Xj. ((i-j) % (K-1) = 0)

2. If t > 1, we have (j-i+1 - t) % (K-1) = 0, 1 < t < j-i+1, and f[i][j][t] = min{f[i][mid][1] + f[mid+1][j][t-1]}. (i ≤ mid < j, (mid-1) % (K-i) = 0)

The time complexity is O(N^2 × (N/K) × (N/K)) = O(N^4 / (K^2)). The space complexity is O(N^3).

Solution 2

If we reverse the whole merging process, it will look like spliting one pile into K piles, then split some of them into K piles… We only need the cost of spliting a pile into K piles.

So we don’t really need to calculate the cost of merging some stones into t(t > K) piles. Now we have:

1. If t = 1, f[i][j][t] = f[i][j][K] + Xi + … + Xj. ((i-j)%(K-1) = 0)

2. If 1 < t ≤ K, because (j-i+1 - t) % (K-1) = 0 only have one solution t0 in (1, K], we have t = t0. So f[i][j][t] = f[i][j][t0] = min{f[i][mid][1] + f[mid+1][j][t0-1]}. (i ≤ mid < j, (mid-i) % (K-1) = 0)

The time complexity is now reduced to O(N^2 × 1 × (N/K)) = O(N^3 / K), but the space comlexity remains the same.

Solution 3

From Solution 2, we know that for (i, j), there’s only one possible value of t. So we don’t need the third dimension anymore.

Now let f[i][j] be the minimal cost of carry out as many merges on [Xi, …, Xj] as possible.

Intuitively, we divide the problem into two subproblems on [Xi, …, Xmid] and [Xmid+1, …, Xj]. That is, carry as many merges as possible on [Xi, …, Xmid] and [Xmid+1, …, Xj] respectively, and then put the piles left together and try to merge.

But is this correct?

Let a = mid - i + 1, b = j - (mid+1) + 1 = j - mid, c = j - i + 1 = a + b.

If we carry out as many merges as possible on [Xi, …, Xmid] and [Xmid+1, …, Xj] respectively, there will be (a-1) % (K-1) +1 and (b-1) % (K-1) + 1 piles left respectively. And there’s

T = (a-1) % (K-1) + 1 + (b-1) % (K-1) + 1 = (a + b - 2) % (K-1) + 2 = (c - 2) % (K-1) + 2

piles left in total.

1. If (c-1) % (K-1) = 0, T = K-2 + 2 = K. (T-1) % (K-1) + 1 = 1.

2. If 1 ≤ (c-1) % (K-1) < K-1, T = (c-1) % (K-1) - 1 + 2 = (c-1) % (K-1) + 1.

In summary, (T-1) % (K-1) + 1 = (c-1) % (K-1) + 1.

So it is correct to divide the problem on [i, j] into two subproblems on [i, mid] and [mid+1, j]. Now we have:

1. If (j-i) % (K-1) = 0, f[i][j] = min{f[i][mid] + f[mid+1][j]} + Xi + … + Xj.

2. Otherwise, f[i][j] = min{f[i][mid] + f[mid+1][j]}, i ≤ mid ≤ j, (mid-i) % (K-1) = 0,

Now the time complexity is still O(N^3 / K), but the space complexity has been reduced to O(N^2).

Code 1

class Solution {
public:
    int n, sum[32];
    
    int mergeStones(vector<int>& stones, int K) {
        n = stones.size();
        if (n == 1)
            return 0;
        
        if ((n-1)%(K-1) != 0)
            return -1;
        
        sum[0] = 0;
        for (int i = 1; i <= n; ++i)
            sum[i] = sum[i-1] + stones[i-1];
        
        vector<vector<vector<int>>> f(n+1, vector<vector<int>>(n+1, vector<int>(n+1)));
        
        for (int j = K; j <= n; ++j) {
            for (int i = j-K+1; i > 0; --i) {
                int len = j-i+1;
                
                for (int t = len; t > 1; t -= K-1) {
                    int cur = INT_MAX / 2;
                    for (int mid = i; mid < j; mid += K-1)
                        if (f[i][mid][1] != -1 && f[mid+1][j][t-1] != -1)
                            cur = min(cur, f[i][mid][1] + f[mid+1][j][t-1]);
                       
                    f[i][j][t] = cur;
                }
                
                if ((len-1)%(K-1) == 0)
                    f[i][j][1] = f[i][j][K] + sum[j] - sum[i-1];
            }
        }
        
        
        return f[1][n][1];
    }
};

Code 2

class Solution {
public:
    int n, sum[32];
    
    int mergeStones(vector<int>& stones, int K) {
        n = stones.size();
        if (n == 1)
            return 0;
        
        if ((n-1)%(K-1) != 0)
            return -1;
        
        sum[0] = 0;
        for (int i = 1; i <= n; ++i)
            sum[i] = sum[i-1] + stones[i-1];
        
        vector<vector<vector<int>>> f(n+1, vector<vector<int>>(n+1, vector<int>(K+1)));
        
        for (int j = K; j <= n; ++j) {
            for (int i = j-K+1; i > 0; --i) {
                int len = j-i+1, t = len;
                while (t > K)
                    t -= K-1;
                
                int cur = INT_MAX / 2;
                for (int mid = i; mid < j; mid += K-1)
                    if (f[i][mid][1] != -1 && f[mid+1][j][t-1] != -1)
                        cur = min(cur, f[i][mid][1] + f[mid+1][j][t-1]);
                       
                f[i][j][t] = cur;
                
                if ((len-1)%(K-1) == 0)
                    f[i][j][1] = f[i][j][K] + sum[j] - sum[i-1];
            }
        }
        
        return f[1][n][1];
    }
};

Code 3

class Solution {
public:
    int n, sum[32];
    
    int mergeStones(vector<int>& stones, int K) {
        n = stones.size();
        if (n == 1)
            return 0;
        
        if ((n-1)%(K-1) != 0)
            return -1;

        sum[0] = 0;
        for (int i = 1; i <= n; ++i)
            sum[i] = sum[i-1] + stones[i-1];
        
        vector<vector<int>> f(n+1, vector<int>(n+1));
        
        for (int j = K; j <= n; ++j)
            for (int i = j-K+1; i > 0; --i) {
                int cur = INT_MAX / 2;
                for (int mid = i; mid < j; mid += K-1)
                    cur = min(cur, f[i][mid] + f[mid+1][j]);
                f[i][j] = cur;
                
                if ((j-i) % (K-1) == 0)
                    f[i][j] += sum[j] - sum[i-1];
            }
        
        return f[1][n];
    }
};