动态规划中的模式 - 2

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

如果一个问题要求您以最佳方式销毁/折叠/合并（或类似）一个数组，那么您应该尝试使用子段上的动态规划来解决它。

让我们得到 dp[l][r] - 索引从 l 到 r 的子段的最佳答案。动力学的重新计算高度依赖于任务，但有以下一般思路：

1) 查看极端元素 l 和 r。如果它们以某种其他方式匹配或互补，那么很可能可以通过 dp[l+1][r-1] 更新 dp[l][r] 的值。否则通过 dp[l][r-1] 或 dp[l+1[r]。

2) 段 [l;r] 不能通过单一结构表示的情况经常发生。那么需要考虑把这个subsegment所有可能的section分成两部分，即从l到r-1遍历元素k，通过dp[l][k]和dp[重新计算dp[l][r] k+1][r]。在更小的子段中，这些部分也被整理出来，因此，实际上，将子段 [l;r] 不仅分为两个部分，而且分成任意数量的部分的选项都被考虑在内。
 

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

如果您需要检查问题中是否存在排列，或者找到匹配的排列数，或类似的东西，那么您应该考虑使用动态子集编程。

主要参数将是一个位掩码，它将显示哪些元素已经包含在排列中，哪些没有。通常还需要第二个参数，指示最后包含哪个元素。

通常可以在图形路径的上下文中看到排列。因此，让我们考虑一个经典的例子——哈密顿路径问题。
哈密​​顿路径是通过图的每个顶点恰好一次的简单路径。它可以简单地表示为长度为 n 的排列，其中 n 是顶点数。此排列中的顺序将指示遍历此路径中的顶点的顺序。

为了检查图中是否存在哈密顿路径，让我们开始动态 dp[mask][last] - 是否有一条简单的路径绕过掩码位掩码中标记为 1 的顶点并在最后一个顶点结束。
初始值将是 dp[2ⁱ][i] = true，其余为 false，这意味着总是有一条空路径从任何顶点开始。
dp[mask][last] 中的值为 true 我们将在“扩展路径”的意义上向前转换。也就是说，我们将寻找在掩码中标记为零的顶点数（我们还没有在途中访问它们），同时从 last 到这个顶点有一条边（路径必须由现有边扩展）。也就是说，我们做 dp[mask | 2^k][k] = true 如果 dp[mask][last] = true AND mask & 2^k = 0（顶点k还没有被访问过）并且最后有一条边->; k.
最终，如果全一位掩码和任何最后一个顶点的参数在 dp 中存在真值，则存在哈密顿路径。