不同价值的硬币围绕圆桌散布。我们可以选择任何硬币，这样对于任何两个相邻的硬币对，至少必须选择一个（也可以选择两者）。在这种情况下，我们必须找到所选硬币的最小可能值。
我必须尊重时间复杂度，所以我没有使用简单的递归暴力，而是尝试使用动态编程来做到这一点。但我得到了错误的答案 - 我的算法不正确。
如果有人可以建议一种算法来动态地执行它，我可以用 C++ 编写自己的代码。硬币的最大数量也是 10^6 ，所以我认为存在 O(n) 解决方案。
编辑：好的，我还添加一个示例。如果桌子周围的硬币价值是 1,2,1,2,2（圆圈），那么通过选择 1st,3rd & 4th(或 5th) 硬币的最小值将是 4。
把所有东西都围成一个圈会妨碍动态规划，因为没有稳定的起点。
如果您知道最佳答案中将包含特定硬币，则可以将其用作起点。重新编号硬币 1 并使用动态规划计算出 1..N 的最佳成本，选择和不选择第 N 个硬币。鉴于此，您可以计算出 1..N+1 的最佳成本，依此类推。
实际上，如果有人告诉您不会选择特定硬币，您也可以使用此方法- 您的起始条件略有不同。或者您可以使用这样一个事实，即如果您知道未选择特定硬币，则必须选择其两侧的两个。
任何硬币要么被选中，要么不被选中，因此你可以通过解决两个动态规划问题来查看两种方式的成本，然后选择最便宜的成本。
我认为以下算法将为您提供最佳解决方案。我没有通过你的代码（对不起）：
我们将在圆圈中选择一个随机点开始。假设它是 1。我们将看看如果它被选中会发生什么。
所以我们选择1。在圆圈中向上移动，您可以选择是否选择2。这可以显示在树中，其中顶部分支表示选择硬币，而下部表示未选择硬币。数字代表所选硬币的总和。
3 = 1 and 2 both selected
/
1
\
1 = 1 selected, 2 not
现在我们继续循环并选择是否选择 3。这给出了一棵树
6 = 1, 2 and 3 selected
/
3
/ \
/ 3= 1 and 2 selected, 3 not
/
1
\
\ 4 = 1 and 3 selected, 2 not
\ /
1
\
1 = 1 selected, 2 and 3 not
现在在那棵树上，我们可以修剪！鉴于您的问题陈述，您必须跟踪哪些硬币被拿走，以确保每枚硬币都被“覆盖”。假设最后 2 个硬币没有被选中。然后您知道必须选择下一个，以免违反您的约束。更重要的是，算法其余部分的可能性仅取决于最后 2 个硬币的选择。
现在查看所有选择了最后一个硬币 (3) 的分支。您只需要保留重量最轻的那个。这两个分支都可以在算法的其余部分中自由选择他们想要的内容。在这种情况下，我们可以安全地移除顶部分支。然后，我们剩下 3 条可能的路径。
现在看看如果我们列举硬币 4 的选择会发生什么
3 7= 1, 2 and 4 selected, 3 not
/ \ /
/ 3
/ \
3 = 1 and 2 selected, 3 and 4 not
1 8 = 1, 3 and 4 selected, 2 not
\ /
\ 4
\ / \
1 4 = 1 and 3 selected, 2 and 4 not
5 = 1 and 4 selected, 2 and 3 not
\ /
1
\
1 = only 1 selected
现在你有6个选择。但是，最低的分支（只选择了 1）是无效的，因为 3 不与任何东西相邻。您可以修剪它以留下 5 个分支。在这 5 个中，有 3 个选择了 4 个（=到目前为止的最后一个硬币），我们可以像以前一样做同样的事情：只保留最便宜的分支。这将分支的数量再次减少到 3 个。
您可以在整个圈子中继续这样做，直到再次开始。那么你应该有3条路径，你可以选择其中最便宜的。如果您从选择硬币 1 开始，这将为您提供最佳解决方案。
现在我们有了选择 1 的最佳解决方案。但是，可能不应该选择 1。可能是它与另一个选择的硬币相邻：硬币 2 或硬币 6。如果我们现在对硬币 2 而不是硬币 1 执行上述算法一次，对硬币 6 执行一次，我们应该得到最佳解决方案。
这种方法依赖于选择硬币 1、2 或 6 的事实。
我希望我的方法可以理解。它相当长，您可以通过使用一些状态转换图来更快地完成它，在该图中您只维护可能的状态（取决于最后 2 个硬币）并进行处理。方法同上，只是更简洁）
O(n) suggestion, by induction. Hmm, I read the wiki now and I found out it counts as dynamic programming. Really a broad term. I had a different understanding of dynamic programming before.
Glossary
We have N coins in N places. Coin values are a[i], where 0 <= i < N. Each coin may be selected or deselected which we express as the sequence of 0 and 1.
Algorithm description
00 is invalid sequence in any place, because it would violate the problem constraints. 111 is also invalid because it is not optimal, 101 is always better.
Sequentially for every place i we calculate 3 best sums, for 3 codes: 01, 10, 11. The code comes from the setting of last 2 coins, that is i-1 and i. So we have best (minimum) sums in variables b01, b02, b11.
We have to start from something sure, so we will apply the algorithm 2 times. One for coin at place 0 set, and one for unset.
At the beginning we try places 0 and 1 and initiate bs directly. b01 = a[1], b10 = a[0], b11 = a[0] + a[1]. However if this is the round in which we choose the first coin to be unset, we can accept only b01 solution. So we assign a big number to b10 and b11. These solutions will be quickly dropped by next algorithm steps. On the second round we will do the opposite: assign big nuber to b01, because first bit must be set.
At step i we have best sums for place i-1 in bs. We compute cs which are the best sums for place i.
c01 = b10 + a[i] // 101 (10 -> 01)
c10 = min(b01, b11) // 010 (01 -> 10) or 110 (11 -> 10)
c11 = b01 + a[i] // 011 (01 -> 11)
That comes from following possibilities:
010 - b01 -> c10
011 - b01 -> c11
100 - invalid
101 - b10 -> c01
110 - b11 -> c10
111 - invalid
Of course we finish each step with assigning best sums back to bs.
When we processed all the coins we must drop the solutions that are incompatible with the initial assumption. Bits i-2, i-1 and 0 must produce valid sequences.
This is example run for 123456 sequence.
A. assume first bit 0
1 a[1] = 2: b01 = 2, b10 = 999, b11 = 999
2 a[2] = 3: b01 = 1002, b10 = 2, b11 = 5
3 a[3] = 4: b01 = 6, b10 = 9, b11 = 1006
4 a[4] = 5: b01 = 13, b10 = 6, b11 = 11
5 a[5] = 6: b01 = 12, b10 = 13, b11 = 19
b10 is unacceptable, we choose better from b01 and b11, which is 12.
B. assume first bit 1
1 a[1] = 2: b01 = 999, b10 = 1, b11 = 3
2 a[2] = 3: b01 = 4, b10 = 3, b11 = 1002
3 a[3] = 4: b01 = 7, b10 = 4, b11 = 8
4 a[4] = 5: b01 = 9, b10 = 12, b11 = 12
5 a[5] = 6: b01 = 18, b10 = 9, b11 = 15
Now b11 is invalid as it would produce 111. So we choose best of b01 and b10, which is 9. Step A gave 12, step B gave 9. 9 is better. This is the result.
I made the above calculations manually, so sorry if there is a mistake in them. However for the first coin unset I computed 2+4+6 and for first coin set the result was 1+3+5. Seems to be right.