Coin Change Problem (Minimum Coins to Make?

mount)

int CoinChange(int[] coins, int amount)
{
int[] dp = new int[amount + 1];

rray.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: