algorithm - 动态编程-硬币更改决策

我在复习算法课程的一些旧笔记，动态编程问题对我来说似乎有点棘手。我有一个问题，我们有无限的硬币供应，有些面额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的值，则从较小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