硬币数组非相邻选取最大金额问题的递归方程求解

嘿，我来帮你理清这个递归方程的问题哈！首先咱们先明确下问题：给定一个包含n个硬币的数组C = [c₁, c₂, …, cₙ]，每个硬币价值都是正整数（允许重复），我们要选出一组不相邻的硬币，让它们的总金额最大。

你自己尝试写的递归式思路方向是对的，但不小心把“选”和“不选”第i个硬币的对应情况搞反啦，咱们一步步推导正确的递归方程：

首先，我们先定义M(i)表示**前i个硬币（也就是从c₁到cᵢ的子数组）**中，能选取到的最大金额。接下来分两种核心情况讨论：

• 不选取第i个硬币：这时候前i个硬币的最大金额，就完全等于前i-1个硬币的最大金额，也就是M(i-1)——毕竟第i个硬币没选，前面的最优解直接沿用就行。
• 选取第i个硬币：因为不能选相邻的硬币，所以第i-1个硬币绝对不能选。这时候总金额就是第i个硬币的价值cᵢ，加上前i-2个硬币的最大金额M(i-2)，也就是M(i-2) + cᵢ。

所以，M(i)的递归方程应该是这两种情况里的最大值，写成数学式就是：

M(i) = max(M(i-1), M(i-2) + cᵢ)

当然，递归需要明确的边界条件才能终止：

• 当i=0（没有硬币可选）时，M(0) = 0；
• 当i=1（只有第一个硬币）时，M(1) = c₁——毕竟只能选这一个硬币，总金额就是它的价值。

咱们用你给的例子C₇ = [5, 20, 2, 20, 1, 10, 50]验证下：

• M(1) = 5
• M(2) = max(5, 0+20) = 20
• M(3) = max(20, 5+2) = 20
• M(4) = max(20, 20+20) = 40
• M(5) = max(40, 20+1) = 40
• M(6) = max(40, 40+10) = 50
• M(7) = max(50, 40+50) = 90

最终得到的最大金额是90，对应的选法是拿第2个（20）、第4个（20）、第7个（50），确实都是不相邻的，总金额也最大，完全符合要求~

备注：内容来源于stack exchange，提问作者Katerina Giorgallou