循环列表中非相邻元素的最大值

Question

鉴于：

• 您有一个循环链接 L，节点为 N1、N2、...N10、N1
• 每个节点都有一个元组 (L,P)，其中 L 是不选择节点的值，P 是选择节点
• 如果你选择一个节点那么你就不能选择它的邻居说如果你选择N1那么你就不能选择N2,N10

如何确定可以获得的最大值？

我知道它是 DP，它类似于列表中非相邻元素的最大总和，但它是一个循环这一事实让我很困惑。

Answer 1

提示：假设有k个节点，可以通过比较两种方案来摆脱循环：

1. 取n₁求解节点n₃,n_{的非循环问题]4}, …, n_k-1, 或

2. 不取n₁并求解节点n₂,n[=21的非循环问题=]3, …, n_k.

这两个解决方案中最好的给出了循环问题的最优解。