位掩码动态规划中的重叠子问题
The overlapping sub problems in bitmask dynamic programming
我正在尝试通过动态编程学习位掩码，但我无法理解案例的重叠子问题。有人可以根据他们认为适合轻松解释的任何示例来解释子问题如何重叠吗？
我不确定这是否是您要问的。但不幸的是，一个不在位掩码问题领域的例子是 DP 的事实上的初学者例子：斐波那契数列。
你可能知道，斐波那契数列的定义大致如下。
F(n) = F(n-1) + F(n-2)
F(0) = F(1) = 1
现在，假设您想找到 F(8)。那么你实际上是在寻找 F(7) + F(6)。要找到 F(7)，您需要 F(6) 和 F(5)。为了找到 F(6)，您需要 F(5) 和 F(4)。
如你所见，F(6)和F(7)都需要求解F(5)，这意味着它们是重叠的。顺便说一句，F(7) 也需要解决整个问题 F(6)，但对于每个 DP 问题而言，情况不一定总是如此。从本质上讲，有时您的 子问题 A 和 B 可能都依赖于较低级别的子问题 C，在这种情况下，它们被认为是重叠的 。
让我们以 Shortest Hamiltonian walk 为例，在这个问题中，我们需要找到最短的哈密顿游走，其中每条边都有一定的权重。
Hamiltonian walk 是我们在图表 exactly once.
中访问 each and every node 的地方
这个问题可以用 DP Bitmasks 来解决，因为节点数很少。所以我们要做的是保持一个 Bitmask 来跟踪我们在当前状态下访问了哪些节点，然后我们可以使用 mask 迭代所有未访问的节点我们可以去不同的州。
现在假设一个子问题 k 没有计算节点，这个 k 节点的解决方案由更小的子问题构成，形成 k 个节点的更大解决方案，即初始解决方案有只有 2 个节点，然后是 3 个，以此类推，当我们到达 kth 节点时。
现在我们来看另一个子问题，假设 m 个节点也存在。
现在从第一个子问题中的一个节点到第二个子问题中的一个节点有一条边，我们想连接这两个子问题，所以在这种情况下 k 个节点的所有较小的子问题都是也是整个组合解决方案的较小子问题，因此这里称为重叠，因为它存在于第一个子问题和较大的组合子问题中。
为了避免这些重叠子问题的冗余计算，我们使用 memoisation 的概念，即一旦我们有了重叠子问题的答案，我们就将其存储起来以备后用。
另请注意，在上述 2 个子问题中，较小的子问题中不应存在顶点，我们可以使用相应的位掩码进行检查。
我正在尝试通过动态编程学习位掩码，但我无法理解案例的重叠子问题。有人可以根据他们认为适合轻松解释的任何示例来解释子问题如何重叠吗？
我不确定这是否是您要问的。但不幸的是，一个不在位掩码问题领域的例子是 DP 的事实上的初学者例子：斐波那契数列。
你可能知道，斐波那契数列的定义大致如下。
F(n) = F(n-1) + F(n-2)
F(0) = F(1) = 1
现在，假设您想找到 F(8)。那么你实际上是在寻找 F(7) + F(6)。要找到 F(7)，您需要 F(6) 和 F(5)。为了找到 F(6)，您需要 F(5) 和 F(4)。
如你所见，F(6)和F(7)都需要求解F(5)，这意味着它们是重叠的。顺便说一句，F(7) 也需要解决整个问题 F(6)，但对于每个 DP 问题而言，情况不一定总是如此。从本质上讲，有时您的 子问题 A 和 B 可能都依赖于较低级别的子问题 C，在这种情况下，它们被认为是重叠的 。
让我们以 Shortest Hamiltonian walk 为例，在这个问题中，我们需要找到最短的哈密顿游走，其中每条边都有一定的权重。
Hamiltonian walk 是我们在图表 exactly once.
each and every node 的地方
这个问题可以用 DP Bitmasks 来解决，因为节点数很少。所以我们要做的是保持一个 Bitmask 来跟踪我们在当前状态下访问了哪些节点，然后我们可以使用 mask 迭代所有未访问的节点我们可以去不同的州。
现在假设一个子问题 k 没有计算节点，这个 k 节点的解决方案由更小的子问题构成，形成 k 个节点的更大解决方案，即初始解决方案有只有 2 个节点，然后是 3 个，以此类推，当我们到达 kth 节点时。
现在我们来看另一个子问题，假设 m 个节点也存在。
现在从第一个子问题中的一个节点到第二个子问题中的一个节点有一条边，我们想连接这两个子问题，所以在这种情况下 k 个节点的所有较小的子问题都是也是整个组合解决方案的较小子问题，因此这里称为重叠，因为它存在于第一个子问题和较大的组合子问题中。
为了避免这些重叠子问题的冗余计算，我们使用 memoisation 的概念，即一旦我们有了重叠子问题的答案，我们就将其存储起来以备后用。
另请注意，在上述 2 个子问题中，较小的子问题中不应存在顶点，我们可以使用相应的位掩码进行检查。