dynamic-programming - 简化硬币兑换算法的动态伪代码

Question

作为一项家庭作业，我们的教授向我们展示了一个简化版的硬币兑换问题，我们不需要最小化使用的硬币数量或跟踪可能的组合数量。相反，我们只需要确定一定数量的相同或不同面额的硬币是否完全相等，一定数量 M。

我的问题的递归方程如下：

let k = 0

If ∑ (v1 + v2 + … + vn) = M   
    return true

If ∑ (v1 + v2 + … + vn) < M
    return false

Else 
    Increment k by 1
    make recursive call on coin subset {v1, v2, … v(n-k)}

下一个问题是将其转换为代表该问题的动态编程解决方案的伪代码。

我有点卡住了。如果您要为每个可能的总和 {v1 + v2}、{v1 + v2 + v3}、{v1 + v2 + v3 + v4} 等制作一个表格。您最终可以找到解决方案，但那不是效率低得多的蛮力方法？

我假设该解决方案将包括一些记忆化的实现或某种存储和检索已经遇到的总和的方法，但由于问题不是优化问题，我很难设想一个动态的解决方案。

我看到的许多动态编程示例都建议迭代地减去元素，一次一个项目，这类似于我的递归方程的组成，但我没有看到可以使这个伪代码在本质上动态的修改。

如果有人可以请赐教，我将不胜感激

标签： dynamic-programmingpseudocodecoin-change