dynamic-programming - 动态规划。硬币行问题 - 如何发展其递归关系

Question

问题：一组 n 个硬币排成一排。硬币具有不需要区分的正值。在不能捡起两个相邻硬币的约束条件下，找出可以收集的最大数量。

其递推关系为

F(n) = max{cn + F(n − 2), F(n − 1)} for n > 1,
F(0) = 0, F(1) = c1.

我的问题是这种递归关系是如何发展的。请有人向我解释一下。

标签： dynamic-programming

Answer 1

首先，设想一行硬币，每个硬币的价值由变量 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