Adn*_*shi 0 dynamic-programming
问题：一组 n 个硬币放在一排。硬币具有不需要不同的正值。考虑到不能捡起两个相邻的硬币的限制，找出可以收集的最大数量。
它的递归关系是
F(n) = max{cn + F(n ? 2), F(n ? 1)} for n > 1,
F(0) = 0, F(1) = c1.
我的问题是这种递归关系是如何发展的。请有人向我解释这一点。
小智 5
首先，设想一行硬币，每个硬币的价值由变量 ci 描述：
c1 c2 c3 c4 c5 ... cn
如果没有硬币，那么显然可以制造的最大数量为 0。同样，如果只有 1 个硬币，则最大数量是该硬币的价值，c1。这说明了基本情况。
对于n 个硬币的最大值的递归情况，从cn最右边的硬币开始。由于约束条件是，你不能选择相邻的硬币，最大值，你可以做到的，是两种最右边的硬币加上2个插槽实现向左最大（这占F（N - 2），或最高达到通过选择紧邻左边的硬币（考虑到 f(n-1) 的情况）并丢弃最右边的硬币 cn。
再次考虑以下硬币行：
c1 c2 c3 c4 c5 c6
f(6) 情况将查看 c6 + 硬币 c1 - c4 中的最大金额，或硬币 c1 - c5 中的最大金额（不包括 c6）。
f(4) 同样返回 c4 + 硬币 c1 - c2 中的最大金额，或硬币 c1 - c3 中的最大金额（同样不包括 c4）。
f(2) 返回 c2 + c0 或 c1 中的最大值（实际上是 c1） 第一个等于 c2，因为 c0 在基本情况下为 0，第二个等于 c1（再次按基本情况）。所以 f(2) 实际上只是 c1 或 c2 的最大值。
还要注意，f(n - 2) 和 f(n - 1)可能相同，因为在 n - 1 的情况下，选择左边的硬币可能是有益的（即 f(n - 2）案例）。但这就是为什么前半部分不仅是 f(n - 2)，而且还加上了 cn