algorithm - 动态规划 - 循环最大加权独立集

我了解 MWIS 算法及其子问题

A[i]=max(A[i-1], A[i-2]+W[i])

但是当它添加使序列为循环的条件时，意味着第一个元素连接到最后一个节点。

我被卡住了，无法找出正确的子问题..

标签： algorithmdynamic-programmingschedulingbipartite

答案其实很简单。假设您在 from 中有一个节点权重列表A，其中A[i]连接到A[i-1]和A[i+1]。

还假设您有一个函数solve()可以解决第一个和最后一个节点未连接的 MWIS 问题。

循环变化的唯一附加标准是，如果第一个节点在集合中，则最后一个节点不能在其中。如果最后一个节点在集合中，则第一个节点不能在其中。

因此，答案只是solve(A[1:])（没有第一个节点的数组的解）和solve(A[:-1])（没有最后一个节点的数组的解）的最大值。

为什么这是正确的？考虑最佳答案。它必须缺少A[0]or A[-1]，因此它必须是A[1:]or的子集A[:-1]。