更改硬币的执行问题

Question

当我试图使用DP解决这个经典问题时，我遇到了一个实现问题。该问题给出了一组硬币，并以返回的方式进行了改变。

DP等式类似于以下内容：DP[i]=DP[i-币[j]]
其中DP[i]表示对i进行更改的方式数。

这里有一个简单的实现，这是不正确的：

int make_change_wrong(int coin[], int size, int change) {
    vector<int> DP(change + 1, 0);
    DP[0] = 1;

    for (int i = 1; i <= change; ++i) {
        for (int j = 0; j < size; ++j) {
            if (i - coin[j] >= 0 ) {
                DP[i] += DP[i - coin[j]];
            }
        }
    }

    return DP[change];
}

给定输入：int coin[]={1,5}change=6。

make_change_wrong（硬币，2,6）返回3，但2是正确的。

使用相同的逻辑，我以不那么直观的方式重新编写，并得到正确的答案：

int make_change(int coin[], int size, int change) {
    vector<int> DP(change + 1, 0);
    DP[0] = 1;

    for (int i = 0; i < size; ++i) {
        for (int j = coin[i]; j <= change; ++j) {
            DP[j] += DP[j - coin[i]];
        }
    }

    return DP[change];
}

这让我很困惑，因为对我来说，他们是一样的。。。有人能解释一下这两个实现中的问题吗？

Answer 1

请尝试输入第二种方法：

coin[5] = {1,5,10,20,30};
make_change(coin,5,30);

它返回21。请检查我的测试用例。

Answer 2

这个问题在面试准备书《破解编码面试》中，书中给出的解决方案根本没有优化。它使用递归（不带DP）来重复计算子问题，因此运行在O（N^3）中，这尤其具有讽刺意味，因为它是动态编程章节的一部分。

下面是一个非常简单的工作解决方案（Java），它使用DP并在O（N）时间内运行。

static int numCombos(int n) {
    int[] dyn = new int[n + 1];
    Arrays.fill(dyn, 0);
    dyn[0] = 1;
    for (int i = 1;  i <= n; i++) dyn[i] += dyn[i - 1];
    for (int i = 5;  i <= n; i++) dyn[i] += dyn[i - 5];
    for (int i = 10; i <= n; i++) dyn[i] += dyn[i - 10];
    for (int i = 25; i <= n; i++) dyn[i] += dyn[i - 25];
    return dyn[n];
}

Answer 3

你的第一个算法是错误的。

DP[5]=2{1,1,1,1}，{5}

DP[6]=DP[5]DP[1]=3

你在数{5,1}两次。经过编辑，这样做的标准诀窍是，你可以对允许使用的面额进行计数

DP[i,m] = DP[i-coin[m],m] + DP[i,m-1]

这意味着使用[1..m]范围内的硬币改变i数量的方法的数量。很明显，你要么使用mth面额，要么不使用。

你正在使用的第二种算法是做同样的把戏，但这是一个非常聪明的方法，拿第i枚硬币，看看你能用它产生什么样的变化。这将避免过度计数，因为您避免执行类似{1,5}和{5,1}的操作。