循环的最大权独立集问题（路径图修改）
Maximum-weight independent set problem for a cycle (path graph modification)
问题： 顶点权重为非负的图 G = (V, E)。
期望输出： 具有 n 个顶点 v1 的循环 C 中最大总权重的一组独立顶点（不相邻）。 . . vn（对于每个 i < n，vi 连接到 vi + 1，vn 连接到 v1，这些是 C 中唯一的边）。
这个问题是这个问题的修改：
我知道原来的路径图不包含圈的问题，解法是
a[i] = max(a[i - 1], a[i - 2] + w[i])
这是因为 IS 可以是包含 vn 或不包含 vn 的，并且 运行 时间是 O(n) 最坏情况，因为每个子问题只占用 n 的一部分并且减少它，因为它是分而治之。
循环修改，我的做法是：
- IS 包含 v1 但不包含 vn，
- IS 包含 vn 但不包含 v1,
- IS 既不包含 v1 也不包含 vn。
我不确定方程是否与循环修改的路径图（如上所示）相同，也不确定如何编写，我不确定 运行 时间仍然是一样的。请帮忙
我们不需要案例不重叠。如果我们找到排除 v1 的解的最大值，以及排除 vn 的解的最大值，那么总的最大值必须与这两个候选解之一相匹配，因为没有解同时包含 v1 和 vn。对于这些子问题，路径 DP 很有效。
问题： 顶点权重为非负的图 G = (V, E)。 期望输出： 具有 n 个顶点 v1 的循环 C 中最大总权重的一组独立顶点（不相邻）。 . . vn（对于每个 i < n，vi 连接到 vi + 1，vn 连接到 v1，这些是 C 中唯一的边）。
这个问题是这个问题的修改：
我知道原来的路径图不包含圈的问题，解法是
a[i] = max(a[i - 1], a[i - 2] + w[i])
这是因为 IS 可以是包含 vn 或不包含 vn 的，并且 运行 时间是 O(n) 最坏情况，因为每个子问题只占用 n 的一部分并且减少它，因为它是分而治之。
循环修改，我的做法是：
- IS 包含 v1 但不包含 vn，
- IS 包含 vn 但不包含 v1,
- IS 既不包含 v1 也不包含 vn。
我不确定方程是否与循环修改的路径图（如上所示）相同，也不确定如何编写，我不确定 运行 时间仍然是一样的。请帮忙
我们不需要案例不重叠。如果我们找到排除 v1 的解的最大值，以及排除 vn 的解的最大值，那么总的最大值必须与这两个候选解之一相匹配，因为没有解同时包含 v1 和 vn。对于这些子问题，路径 DP 很有效。