在流行的 Coin-Change 动态规划问题中遍历状态的正确顺序是什么？

Question

我在 Hackerrank 上解决了这个（https://www.hackerrank.com/challenges/coin-change/copy-from/188149763）问题，总结如下：

Find the total number ways to exchange a certain value with the given set of coin denominations.

这是我被接受的代码：

long getWays(int n, vector<long> c) {
    long dp[n+1];
    memset(dp, 0ll, sizeof(dp));
    dp[0] = 1;
    for(int ci=1; ci<=c.size(); ci++)
    {
        for(int i=1; i<=n; i++)
        {
            if(c[ci-1] > i) continue;
            dp[i] += dp[i-c[ci-1]];
        }
    }
    return dp[n];
}

这里n是我们应该得到的总值，c是硬币数组。我的问题是，如果我颠倒循环的顺序，即做类似

的事情

long getWays(int n, vector<long> c) {
    long dp[n+1];
    memset(dp, 0ll, sizeof(dp));
    dp[0] = 1;
    for(int i=1; i<=n; i++){
        for(int ci=1; ci<=c.size(); ci++)
        {
            if(c[ci-1] > i) continue;
            dp[i] += dp[i-c[ci-1]];
        }
    }
    return dp[n];
}

为什么答案变了？

Answer 1

第一个代码更新了用新硬币组合值 dp[i] 的方法数。在第 k 轮外循环后，我们得到 dp[] 数组，其中仅填充了 k 个硬币的组合，其余硬币尚未使用。如果我们自己为 sorted 硬币列表输出组合，我们将看到 ordered 像 1 1 5 - 5 never will go before 1 .

第 m 轮外循环的第二个程序使用所有可能的硬币填充第 m 个单元格 dp[m]。所以我们可以得到 m=7 1 1 5 和 1 5 1 以及 5 1 1 - 所有可能的排列。这就是结果不同的原因。

在流行的 Coin-Change 动态规划问题中遍历状态的正确顺序是什么？

What is the correct order to traverse the states in the popular Coin-Change dynamic programming question?

c++

algorithm

dynamic-programming

coin-change