我正在尝试通过动态编程学习位掩码，但我无法理解案例的重叠子问题。有人可以根据他们认为适合轻松解释的任何示例来解释子问题如何重叠吗？
最佳答案
让我们以最短哈密顿游走为例，在这个问题中，我们需要找到最短的哈密顿游走，其中每条边都有一定的权重。
Hamiltonian walk 是我们访问图中的每个节点恰好一次。
对于少量节点，可以使用 DP 位掩码 解决此问题。所以我们要做的是保留一个 Bitmask 来跟踪我们在当前状态下访问了哪些节点，然后我们可以使用 mask 迭代所有未访问的节点> 我们可以去不同的州。
现在假设一个子问题 k 没有计算节点，这个 k 节点的解决方案由更小的子问题构成，形成更大的 k 节点解决方案，即初始解决方案只有 2 个节点，然后是 3 个，以此类推，当我们到达 kth 节点时。
现在我们来看另一个子问题，假设 m 个节点也存在。
现在从第一个子问题中的一个节点到第二个子问题中的一个节点有一条边，我们想加入这两个子问题，所以在这种情况下，k 节点的所有较小的子问题也是整个组合解决方案的较小子问题，因此这里称为重叠，因为它存在于第一个子问题和较大的组合子问题中。
为了避免这些重叠子问题的冗余计算，我们使用内存的概念，即一旦我们得到重叠子问题的答案，我们就将其存储起来以备后用。
另请注意，在上述 2 个子问题中，较小的子问题中不应存在顶点，我们可以使用相应的位掩码进行检查。
关于algorithm - 位掩码动态规划中的重叠子问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36180200/