我回顾了一些旧的笔记从我的算法场和动态规划问题似乎有点麻烦我。我有一个问题，我们有无限供给的硬币，一些教派X1，X2，... Xn和我们要改变一些值X。我们正在努力设计一个动态的方案，以决定是否变化X可以作出或不（不减少硬币的数量，或返回该硬币，只是真或假）。

I'm reviewing some old notes from my algorithms course and the dynamic programming problems are seeming a bit tricky to me. I have a problem where we have an unlimited supply of coins, with some denominations x1, x2, ... xn and we want to make change for some value X. We are trying to design a dynamic program to decide whether change for X can be made or not (not minimizing the number of coins, or returning which coins, just true or false).

我已经做了关于这个问题的一些思考，我可以看到这样做的递归方法，其中它的东西，就像...

I've done some thinking about this problem, and I can see a recursive method of doing this where it's something like...

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;

转换这是一个动态的方案不来那么容易给我。我会如何处理这个？

Converting this a dynamic program is not coming so easily to me. How might I approach this?

推荐答案

您code是一个良好的开端。通常的方法来递归解决方案转换为动态编程之一就是做自下而上而非自上而下。也就是说，如果您的递归解一些计算使用值较小的X A特定的X，然后计算出，而不是在较小的X同样的事情的启动的，并把它放在一个表中。

Your code is a good start. The usual way to convert a recursive solution to a dynamic-programming one is to do it "bottom-up" instead of "top-down". That is, if your recursive solution calculates something for a particular X using values for smaller x, then instead calculate the same thing starting at smaller x, and put it in a table.

在你的情况，改变你的MakeChange递归函数成canMakeChange表。

In your case, change your MakeChange recursive function into a canMakeChange table.

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