2

在尝试使用 DP 解决这个经典问题时，我遇到了一个实现问题。问题是给定一组硬币，并返回做出改变的方式的数量。

DP 方程类似于以下内容： DP[i] += DP[i - coin[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(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];
}

这让我很困惑，因为对我来说，它们是同一件事......有人可以说明一下这两种实现中的问题吗？

4

3 回答 3

4

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

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} 之类的操作。

于 2013-07-05T05:08:36.633 回答
0

请尝试输入您的第二种方法：

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

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

于 2013-10-21T12:40:35.867 回答
0

这个问题在面试准备书Cracking the Coding Interview中，书中给出的解决方案根本没有优化。它使用递归（没有 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];
}
于 2013-07-26T04:16:34.277 回答