动态规划-硬币变化决策

我正在复习算法课程中的一些旧笔记，动态规划问题对我来说似乎有点棘手。我遇到一个问题，我们有无限供应的硬币，其中一些面额为 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