Min coins
dp[amount] = min coins to make amount. Init dp[0]=0, rest infinity.
for (int a = 1; a <= amount; a++)
for (int c : coins)
if (a >= c) dp[a] = min(dp[a], dp[a - c] + 1);Advertisement
Number of ways
dp[amount] = # ways to make amount. Iteration order matters!
dp[0] = 1;
for (int c : coins) // OUTER = coins
for (int a = c; a <= amount; a++) // INNER = amount
dp[a] += dp[a - c];Advertisement
Why iteration order matters
Ways counting: outer loop = coins prevents counting {1,2} and {2,1} as different. Ordered counting.
Min coins
dp[amount] = min coins to make amount. Init dp[0]=0, rest infinity.
for (int a = 1; a <= amount; a++)
for (int c : coins)
if (a >= c) dp[a] = min(dp[a], dp[a - c] + 1);Number of ways
dp[amount] = # ways to make amount. Iteration order matters!
dp[0] = 1;
for (int c : coins) // OUTER = coins
for (int a = c; a <= amount; a++) // INNER = amount
dp[a] += dp[a - c];Why iteration order matters
Ways counting: outer loop = coins prevents counting {1,2} and {2,1} as different. Ordered counting.
Impossible amounts
If dp[amount] stays infinity (or 0 for ways), no solution. Return -1 or 0.