动态规划中的模式

免责声明：下面描述的方法并不通用，但它通常可以解决问题或帮助您找到正确的解决方案。

如果问题归结为需要以最佳方式（或计算合适的拆分次数）将数组拆分为不相交的子段（一系列连续元素），那么值得尝试解决它使用动态规划。

示例解决方案如下：
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]

如果需要把数组恰好分成k个子段，那么在动态规划中只需要加上第二个参数——分成多少段。
即，现在我们将考虑以下 dp：
dp[i][j] 是前 i 个元素的答案，如果我们将它们分成恰好 j 个部分。
注意无效状态。

动力学的重新计算是相同的，但考虑了第二个参数。即统计dp[i][k]并通过最后一个子段j的左边界进行排序，我们通过dp[j - 1][k - 1]和段的值重新计算dp[i][k] [j;i]。

免责声明：下面描述的方法并不通用，但它通常可以解决问题或帮助您找到正确的解决方案。

如果在某个轴上有一组间隙（通常是时间轴或某个数组的索引）并且您需要以最佳方式选择其中的一些间隙以使所选间隙不相交，那么您应该尝试使用动态规划.

大概的解决方案：

最初，我们按右边界对可用间隙进行排序。让我们开始以下动态：dp[i] - 前 i 个区间的答案。 
我们将重新计算如下：首先考虑不使用这个区间的情况，那么只要dp[i] = dp[i-1]。注意，这样可以保证dp[i]的值不会随着i的增长而减少。这是合乎逻辑的，因为。添加一个新的差距，我们不能恶化全局答案：要么我们简单地忽略新的差距，要么我们使用它构建一个更有利可图的变体。现在，如果我们想使用第 i 个间隙，那么我们可以使用右边界小于当前间隙左边界的那些间隙，因为我们必须选择一组不重叠的间隙。为此，我们最初按右边界对间隙进行排序，以便现在我们可以有效地找到所需的位置。如果可能的话，这可以通过分析来完成，但在一般情况下，可以通过 binsearch 找到一个间隙，其右边界小于当前边界的左边界，同时，最大可能一。出于贪婪的原因，我们想最大化右边界，因为随着我的成长，答案只会越来越多。因此，我们找到所需的位置 p 并通过 dp[p] 和第 i 个间隔重新计算 dp[i]。