Disclaimer: The method described below is not universal, but it can often solve a problem or help you come to the right solution.
If the problem boils down to the fact that it is necessary to split the array into non-intersecting subsegments (a sequence of consecutive elements) in an optimal way (or count the number of suitable splits), then it is worth trying to solve it using dynamic programming.
An example solution scheme is as follows:
dp[i] - response for the first i elements
Counting dp[i]: since we are only considering the first i elements, the i-th element will be the last one, which means that this element will be in the last subsegment and, at the same time, the rightmost one there. Therefore, we can iterate over the left boundary of the last subsegment j. In the process of enumeration, we will calculate the value of this subsegment, and if it is correct, then we will recalculate dp[i] through dp[j - 1] and the value of the subsegment [j;i].
Consider the following simple problem: given an array of integers, you need to split it into the minimum number of non-intersecting subsegments so that each number is included in some subsegment and that each subsegment contains the same numbers. For example, for an array 1 2 2 3 3 3 2 1 1, the optimal partition looks like this: [1] [2 2] [3 3 3] [2] [1 1]. This task is easily solved by simply passing through the array (we put all the same consecutive elements in one subsegment), but we will solve it using dynamic programming for an example.
intn;
cin>> n;
// fill array with 1-index
vector arr(n + 1);
for (int i = 1; i <= n; i++)
cin>> arr[i];
// initially set +oo to dp values
vector dp(n + 1, 1000000000);
// an array of length zero does not need to be split, so the answer for it is 0
dp[0] = 0;
// count the answer for dp[i] in ascending i
for (int i = 1; i <= n; i++) {
// currently arr[i] is the last element, so it will be the rightmost number in the last subsegment
// loop through all the options for where this last subsegment started
for (int j = i; j > 0; j--) {
if (arr[j] != arr[i]) {
// if you meet an element that is not equal to the last one, then the subsegment will contain different numbers, and this does not fit the condition
// there is no point in continuing, because shifting the left border to the left, this element will not disappear, so we do break
break;
}
// imagine the last subsegment was [j;i]
// so you need to take the optimal partition of the first j-1 elements and add 1 (the subsegment [j; i] itself)
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
cout << dp[n];
If the elements may not belong to any of the subsegments, then you just need to consider the appropriate option, as dp[i] = dp[i - 1]
|
If it is necessary to divide the array into exactly k subsegments, then the second parameter is simply added in dynamic programming - how many segments to split into.
That is, now we will consider the following dp:
dp[i][j] is the answer for the first i elements, if we split them into exactly j segments.
Watch out for invalid states.
The recalculation of the dynamics is the same, but taking into account the second parameter. That is, counting dp[i][k] and sorting through the left border of the last subsegment j, we recalculate dp[i][k] through dp[j - 1][k - 1] and the value of the segment [j;i].
|
Disclaimer: The method described below is not universal, but it can often solve a problem or help you come to the right solution.
If there is a set of gaps located on some axis (usually the time axis or indices of some array) and you need to choose some of them in an optimal way so that the selected gaps do not intersect, then you should try using dynamic programming.
Approximate solution scheme:
Initially, we sort the available gaps by the right border. Let's start the following dynamics: dp[i] - the answer for the first i intervals.
We will recalculate as follows: first, consider the situation that this interval will not be used, then just dp[i] = dp[i-1]. Note that this ensures that the values of dp[i] do not decrease as i grows. And this is logical, because. adding a new gap, we cannot worsen the global answer: either we simply ignore the new gap, or we construct a more profitable variant using it. Now, if we want to use the i-th gap, then we can use those gaps whose right borders are less than the left border of the current gap, since we must choose a set of non-overlapping gaps. To do this, we initially sorted the gaps by the right border, so that now we can efficiently find the required position. This can be done analytically, if possible, but in the general case it is possible to find a gap with a binsearch, the right border of which is less than the left border of the current one and, at the same time, the maximum possible one. We want to maximize the right border for greedy reasons, because as i grows, the answer can only increase. Accordingly, we find the required position p and recalculate dp[i] through dp[p] and the i-th interval.
|