The Coin Change problem: given coin denominations and a target amount, find the minimum number of coins to make the amount. DP solves it with dp[i] = min coins for amount i. For each amount i and each coin c, dp[i] = min(dp[i], dp[i-c]+1). This is the unbounded knapsack variant.
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount+1, INT_MAX);
dp[0]=0;
for(int i=1;i<=amount;i++)
for(int c:coins)
if(c<=i && dp[i-c]!=INT_MAX)
dp[i]=min(dp[i], dp[i-c]+1);
return dp[amount]==INT_MAX ? -1 : dp[amount];
}dp[0]=0 (zero coins needed for amount 0). For each amount i: dp[i] = min over all coins c of (dp[i-c]+1), if i>=c. Initialize all dp[i]=infinity to signify impossible.
Process amounts from 1 to target in order. When computing dp[i], all dp[i-c] are already computed since i-c < i. The nested loop over all coins handles all denominations.
A variant asks for the number of ways to make the amount. Change the recurrence to dp[i] += dp[i-c] for each coin. This counts combinations (order doesn't matter) vs permutations (change loop order).
Quiz coming soon for this algorithm.