algorithm - 更改硬币实现问题

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];
}

给定输入:整数硬币[] = {1, 5}变化 = 6。

make_change_wrong(coin, 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

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

DP[5] = 2 {1,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 数量的方法的数量。这显然是，你要么使用第 m 个面额，要么不使用。

您使用的第二个算法是做同样的事情，但这是一种非常聪明的方法，拿第 i 个硬币，看看使用它可以产生什么变化。这将避免过度计数，因为您避免做 {1,5} 和 {5,1} 之类的事情。