Characteristics of interval DP: Can integrate two or more parts, or vice versa; can decompose a problem into a form that can be combined in pairs.
Solution to interval DP: YesSet the optimal value for the entire problem, enumerationmerge point, decompose the problem intoleft and right parts, and finally combine the optimal values of the two parts to obtain the optimal value of the original problem.
The general method is to enumerate the length (outermostL, 0 < L < N), enumerate the left endpoint (second leveli, 0 < i < N-L), from which the right endpoint can be determined (j = i + L), enumerate merge points (i <= t < j).
What is an enumeration merge point? It’s like I want to merge theicentimeters to the 1stjIf you cut a centimeter directly, where can you cut it?i~jThe cut in between is the merge point, which requires a loop to enumerate.
Merge of stones
There are N piles of stones arranged in a row, numbered 1, 2, 3,...,N.
Each pile of stones has a certain mass, which can be described by an integer. Now we need to merge these N piles of stones into a pile.
Only adjacent ones can be merged each timetwo piles, the cost of merging is the sum of the masses of the two piles of stones. After merging, the stones adjacent to the two piles of stones will be adjacent to the new pile. Due to the different selection order during merging, the total cost of merging is also different.
For example, there are 4 piles of stones, respectively 1 3 5 2. We can first merge piles 1 and 2 at a cost of 4 to get 4 5 2, then merge piles 1 and 2 at a cost of 9 to get 9 2, and then merge them to get 11. The total cost is 4+9+11=24;
If the second step is to merge heaps 2 and 3 first, the cost is 7, resulting in 4 7. The last merge cost is 11, and the total cost is 4+7+11=22.
- Ideas
Classic interval DP. Two dimensions are quite standard.
This question will be easy to remember because the sub-problem is "Merge theiobject to thej"the optimal solution for each object", while the original problem is "the merged1object to theNThe optimal solution for an object".
class Solution{ public int mergeStones(int[] a){ int[] arr = new int [a.length+1]; int N = a.length; for(int i = 1;i <= N;i++){ arr[i] += a[i-1]; } for(int i = 1;i <= N;i++){ arr[i] += arr[i-1]; } //prefix sum int [][] dp = new int [N+1][N+1]; for(int l = 2;l <= N;l++){ //The length of the enumeration interval - the distance between i and j for(int i = 1;i + l <= N+ 1;i++){ //Enumerate the left endpoint int j = i + l -1; dp[i][j] = Integer.MAX_VALUE; for(int k = i;k<j;k++){ //k is the merge point. Merge points are enumerated here, and all are considered from i to j. dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+(arr[j] - arr[i-1])); } } } return dp[1][N]; }
}
Minimum Cost to Merge Stones
This question gives us N piles of stones. Each pile of stones has a different number. It is said that K piles of stones can be merged each time. The cost of merging piles is the number of stones. Then we ask how to merge them to minimize the total cost. Then some examples were given. By observing the examples, we can find that not all inputs can be successfully combined into one pile. For example, in Example 2, no matter which three piles are merged first, there will eventually be two piles left, making further merging impossible. Because K=3, at least three piles need to be merged each time. Of course, we hope to know whether we can successfully merge into a pile before we start merging, instead of only finding out at the end that we have been busy in vain, so we need to analyze when we can finally merge into a pile. Let’s look at Example 2 again. Each time you want to merge three piles into one pile, you will reduce two piles. To make sure that one pile is left in the end, the others must be merged and adjusted. Assume that there are n piles in total and only one pile is left. That means n-1 piles will be reduced, and only k-1 piles can be reduced each time. So as long as n-1 can divide k-1, that is, (n-1)%(k-1) == 0 is true, so you can judge in advance.
Okay, let’s continue and think about how to solve the problem. First of all, we must realize that there may be many situations in this problem. Brute force search may be very complicated, and the current merging method will completely affect subsequent merging, so basically we should give up the idea of Brute force. Similarly, the greedy algorithm cannot be used for this problem. Merging the three piles with the smallest number of stones each time will converge to a local peak, which is not necessarily global, so we can only find another way. Observing that this question is about playing with arrays and looking for extreme values, then we have to use the artifact Dynamic programming Dynamic Programming. Let's consider defining the dp array first. The simplest and most direct method is definitely to use a two-dimensional dp array directly, where dp[i][j] represents the minimum cost of the pile of stones within the merged range [i, j], and finally dp[0][n-1] is the required value. I saw someone on the forum defining a three-dimensional dp array, and the number of heaps K merged each time was also treated as one dimension and put into the dp array. In fact, the blogger felt that it was not necessary, because such a dimension-upgrading operation on the dp array is necessary when there is hidden information in the question, and the currently defined dp array cannot reproduce the sub-problem, that is, it must be done when the state transition equation cannot be found.
According to the previous experience of playing balloons, we need to update from a small interval, how small, starting from K, because the interval smaller than K does not need to be updated, and its dp value must be 0, because K piles of stones must be merged each time, so the length of the interval len traverses from K to n. Okay, the length of the interval is determined. Now we need to determine the starting point. Just traverse i from 0 to n-len. With the starting point and length of the interval, we can determine the end point of the interval j = i+len-1. The goal is to update the dp value in the interval [i, j], first initialized to the maximum integer value. The next update method, the state transition equation, is the biggest difficulty of this question. The dp value of the required interval [i, j] cannot be obtained directly. However, since the update is started from a small interval, suppose the dp values of the small intervals have been updated, and the large interval can be split into two small intervals for update. Generally speaking, when splitting an array into two non-empty sub-arrays, all its situations will be traversed, such as [1, 2, 3, 4], which will be split into [1] and [2,3,4], [1,2] and [3,4], [1,2,3] and [4]. However, due to its particularity, this question does not need to traverse all split situations, because some intervals cannot be obtained by merging piles of stones. Take the above example, if K=3, then there is no need to update the entire interval with [1,2] and [3,4]. They are less than 3 and cannot be merged, so when traversing, just skip K-1 positions each time. Use t to separate the intervals [i, j], and then t += K-1 each time. Use two small intervals. dp value to update the entire interval. This is not over yet. When a certain sub-interval can be merged into a pile of stones, its dp value should be added to the number of all stones in the interval. Take the simplest example, such as [1, 2, 3], K=3, then if we divide, we can only use dp[0] [0]+ dp[1] [2] to update dp[0] [2], but dp[0] [0] and dp[1] [2] are both 0, because the interval lengths are both less than 3, then our dp[0][2] The value cannot be updated to the correct value. These three numbers can be combined, so the sum of all the numbers in the interval must be added. In order to quickly find the sum of any interval, the cumulative sum array sums is established in advance to improve calculation efficiency, so the entire state transition equation is:
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)
With the state transition equation, we can write the code as follows:
class Solution {
public: int mergeStones(vector<int>& stones, int K) { int n = stones.size(); if ((n - 1) % (K - 1) != 0) return -1; vector<int> prefix(n + 1); for (int i = 1; i <= n; ++i) { prefix[i] = prefix[i - 1] + stones[i - 1]; } vector<vector<vector<int>>> f(n, vector<vector<int>>(n, vector<int>(K + 1, 0x3f3f3f3f))); for (int i = 0; i < n; ++i) { f[i][i][1] = 0; } for (int len = 2; len <= n; ++len) { for (int i = 0; i <= n - len; ++i) { int j = i + len - 1; for (int k = 2; k <= K; ++k) { for (int m = i; m < j; m += K - 1) { f[i][j][k] = min(f[i][j][k], f[i][m][1] + f[m + 1][j][k - 1]); } } f[i][j][1] = f[i][j][K] + prefix[j + 1] - prefix[i]; } } return f[0][n - 1][1]; }
};