免责声明:下面描述的方法并不通用,但它通常可以解决问题或帮助您找到正确的解决方案。
如果问题归结为需要以最佳方式(或计算合适的拆分次数)将数组拆分为不相交的子段(一系列连续元素),那么值得尝试解决它使用动态规划。
示例解决方案如下:
dp[i] - 对前 i 个元素的响应
计算 dp[i]:因为我们只考虑前 i 个元素,所以第 i 个元素将是最后一个,这意味着该元素将在最后一个子段中,同时也是那里最右边的一个。因此,我们可以迭代最后一个子段 j 的左边界。在枚举的过程中,我们会计算这个subsegment的值,如果正确,那么我们会重新计算dp[i]到dp[j - 1]和subsegment[j;i]的值。
考虑以下简单问题:给定一个整数数组,您需要将其拆分为最少数量的不相交子段,以便每个数字都包含在某个子段中,并且每个子段包含相同的数字。例如,对于数组 1 2 2 3 3 3 2 1 1,最佳分区如下所示:[1] [2 2] [3 3 3] [2] [1 1]。这个任务很容易通过简单地遍历数组来解决(我们将所有相同的连续元素放在一个子段中),但我们将使用动态规划来解决它作为一个例子。
国际;
辛>>名词;
// 用 1-index 填充数组
矢量 arr(n + 1);
for (int i = 1; i <= n; i++)
辛>>到达[我];
// 最初将 +oo 设置为 dp 值
矢量 dp(n + 1, 1000000000);
// 长度为零的数组不需要拆分,所以它的答案是 0
dp[0] = 0;
// 将 dp[i] 的答案按 i 升序计数
对于 (int i = 1; i <= n; i++) {
// 当前 arr[i] 是最后一个元素,因此它将是最后一个子段中最右边的数字
// 遍历最后一个子段开始位置的所有选项
for (int j = i; j > 0; j--) {
如果 (arr[j] != arr[i]) {
// 如果遇到不等于最后一个的元素,那么子段会包含不同的数字,这不符合条件
// 继续没有意义,因为将左边框向左移动,这个元素不会消失,所以我们 break
休息;
}
// 假设最后一个子片段是 [j;i]
// 所以你需要对前 j-1 个元素进行最优划分并加 1(子段 [j; i] 本身)
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
输出 << dp[n];
如果元素可能不属于任何子段,那么您只需要考虑适当的选项,如 dp[i] = dp[i - 1]