在流行的Coin-Change动态编程问题中遍历状态的正确顺序是什么? [英] What is the correct order to traverse the states in the popular Coin-Change dynamic programming question?

问题描述

我正在解决此问题( https://www.hackerrank.com/challenges/coin-change/copy-from/188149763 )在 Hackerrank 上的问题，可以总结如下:

I was solving this(https://www.hackerrank.com/challenges/coin-change/copy-from/188149763) problem on Hackerrank which can be summarized as follows :

找到用给定的硬币面额交换特定值的总数方法.

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 是硬币的数组.我的问题是我是否可以颠倒循环的顺序，即执行类似

Here n is the total value we are supposed to get and c is the array of coins. My question is if I reverse the order of loops i.e. do something like

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

答案为什么会改变?

推荐答案

第一个代码更新了用新硬币组成值 dp [i] 的多种方法.在第k次外循环之后，我们的 dp [] 数组仅填充了k个硬币的组合，其余硬币尚未使用.如果我们自己输出组合以生成 sorted 硬币列表，我们将看到 ordered 这样的硬币，例如 1 1 5 -5永远不会排在1之前.

The first code updates number of ways to compose values dp[i] with new coin. After k-th round of outer loop we have dp[] array filled with combinations of k coins only, and the rest of coins is not used yet. If we make output of combinations themselves for sorted coin list, we will see ordered ones like 1 1 5 - 5 never will go before 1.

在第m次外循环中的第二个程序使用所有可能的硬币填充第m个单元格 dp [m] .因此我们可以同时获得 m = 7 和 1 1 5 和 1 5 1 和 5 1 1 -全部可能的排列.这就是为什么结果不同的原因.

The second program at m-th round of outer loop fills m-th cell dp[m] using all possible coins. So we can get for m=7 both 1 1 5 and 1 5 1 and 5 1 1 - all possible permutations. That's why result differs.

这篇关于在流行的Coin-Change动态编程问题中遍历状态的正确顺序是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！