1000. Minimum Cost to Merge Stones

Description

image-20210827225529258

image-20210827225539779

Solution

Using DP to solve the problem, we have 

1
dp[i][j][k] = from ith to jth, the cost to form k's piles

So we have

1
dp[i][j][k] = min(dp[i][p][1] + dp[p+1][j][k-1]) (p from i to j-1, step is k-1)

Code

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
class Solution {
public:
    int mergeStones(vector<int>& stones, int k) {
        if((stones.size()-1) % (k-1) != 0)
            return -1;
        int n = stones.size();
        vector<int> prefix(n+1);
        vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(n+1, vector<int>(k+1, 9999999)));
        for(int i = 1; i <= n; i ++){
            prefix[i] = prefix[i-1] + stones[i-1];
        }
        //initializing...
        for(int i = 1; i <= n; i++){
            dp[i][i][1] = 0;
        }
        //DP
        for(int len = 2; len <= n; len++){
            for(int i = 1; i + len - 1 <= n; i++){
                int j = i + len - 1;
                for(int m = 2; m <= k; m++){
                    for(int p = i; p < j; p+=k-1){
                        dp[i][j][m] = min(dp[i][j][m], dp[i][p][1] + dp[p+1][j][m-1]);
                    }
                }
                dp[i][j][1] = dp[i][j][k] + prefix[j] - prefix[i-1];
            }
        }
        return dp[1][n][1];
    }
};