在流行的硬币变化动态编程问题中，遍历状态的正确顺序是什么？

Question

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

找到与给定的硬币面额集合交换某个值的总方法。

这是我被接受的代码：

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个硬币的组合，其余的硬币还没有使用。如果我们为排序的硬币列表输出组合本身，我们会看到像1 1 5-5这样的有序组合永远不会出现在1之前。

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