硬币的动态规划问题

Question

有一系列 𝑛 硬币，其值为 𝐶 = [𝑐1, 𝑐2, … , 𝑐𝑛]。价格 是正整数并且允许重复。例如，一个 可能的硬币序列如下：𝐶7 = [5, 20, 2, 20, 1, 10, 50]。你的目标 就是在你得不到的限制下收取最大金额的钱 两枚硬币并排放置在原来的一排中。例如，如果 从 𝐶7 获得金币 10，则无法获得金币 1 或 50。

你能给我这个问题的递归方程吗？

我尝试过这个，但我不确定：

M(i) = max{ M(i−1), if we take the coin i
            M(i−2)+C[i], if we don't take the coin i

Answer 1

您的解决方案对我来说看起来很正确，只是您的标签颠倒了。

+ C[i]

对应于拿硬币

i

，而不是相反。

如果您还没有的话，我还会添加一个基本案例。

请注意，这是“入室抢劫问题”，因此网上有大量解决方案可供您比较。