Coin Change Problem (Minimum Coins to Make?

Amount)

int CoinChange(int[] coins, int amount)

int[] dp = new int[amount + 1];

Array.Fill(dp, amount + 1);

dp[0] = 0;

for (int i = 1; i <= amount; i++)

foreach (int coin in coins)

if (coin <= i)

dp[i] = Math.Min(dp[i], 1 + dp[i - coin]);

return dp[amount] > amount ? -1 : dp[amount];

Explanation:

Bottom-up DP: min coins needed for all amounts up to target.

Follow on: