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

1
votes

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.

Here is my code which got accepted:

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

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

Why does the answer change?

1
c++algorithmdynamic-programmingcoin-change
long dp[n+1]; -- This is not valid C++. Valid C++ is std::vector<long> dp(n+1,0);, and then you don't need that memset. - PaulMcKenzie
Why does the answer change ? -- Use the debugger and step through the code. - PaulMcKenzie
You are using dp[i-c[ci-1]] to calculate dp[i]. It only works if dp[i-c[ci-1]] is already calculated. Therefore the order is important. - Thomas Sablik

1 Answers

2
votes

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.

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.