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]