我正在复习算法课程中的一些旧笔记，动态规划问题对我来说似乎有点棘手。我遇到一个问题，我们有无限供应的硬币，其中一些面额为 x1、x2、...xn，并且我们想要对某个值 X 进行找零。我们正在尝试设计一个动态程序来决定 X 的找零是否可以是否制造（不是最小化硬币数量，或返回哪些硬币，只是真或假）。
我已经对这个问题进行了一些思考，我可以看到一种递归方法，它类似于......
MakeChange(X, x[1..n this is the coins])
for (int i = 1; i < n; i++)
{
if ( (X - x[i] ==0) || MakeChange(X - x[i]) )
return true;
}
return false;
将其转换为动态程序对我来说并不容易。我该如何处理这个问题？
您的代码是一个好的开始。将递归解决方案转换为动态编程解决方案的通常方法是“自下而上”而不是“自上而下”。也就是说，如果您的递归解决方案使用较小 x 的值计算特定 X 的某些内容，则改为计算相同的内容starting在较小的 x 处，并将其放入表中。
根据您的情况，将 MakeChange 递归函数更改为 canMakeChange 表。
canMakeChange[0] = True
for X = 1 to (your max value):
canMakeChange[X] = False
for i=1 to n:
if X>=x[i] and canMakeChange[X-x[i]]==True:
canMakeChange[X]=True
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
