How it works
Dynamic programming solves a larger problem using already solved smaller subproblems. best[sum] stores the minimum number of coins needed for that exact sum. For each possible final coin, the algorithm considers the best answer for the remaining amount plus one more coin, then keeps the smallest candidate.
For denominations one, three, and four, amount six needs two coins: three plus three. A greedy choice of four first would need three coins after adding two ones. The example demonstrates why a locally attractive choice is not a proof of global optimality for arbitrary denomination systems.
The base case best[0] is zero. Other entries start at a sentinel larger than any feasible count for a positive-coin solution within this bounded amount. If the final entry remains unreachable, the helper returns negative one. Amount zero correctly requires no coins, while amount five using only four and six is unreachable.
Positive denominations are a precondition. A zero or negative coin would break the intended dependency on smaller nonnegative sums. The implementation also allocates an array proportional to amount, so callers need a practical size bound; this teaching helper is not an unrestricted interface for enormous integer amounts.
Practice with an empty denomination set, a single denomination, repeated denominations, and an unreachable amount. Compare results with a small exhaustive search for tiny inputs. Then store the selected final coin for each improved sum and reconstruct an actual optimal combination.
Finally, state whether coins can be reused without limit. This recurrence assumes unlimited copies of each denomination. A limited inventory requires a different state or transition rule. The correctness argument depends on the state meaning, base case, allowed transitions, and input constraints together, not merely on recognizing a loop as dynamic programming.
A working example
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
using System.Text.Json;
using System.Text.Json.Serialization;
using System.Threading;
using System.Threading.Tasks;
using System.Runtime.CompilerServices;
Console.WriteLine(MinCoins(new[] { 1, 3, 4 }, 6));
Console.WriteLine(MinCoins(new[] { 4, 6 }, 5));
Console.WriteLine(MinCoins(new[] { 1, 3, 4 }, 0));
static int MinCoins(int[] coins, int amount) {
if (amount < 0 || coins.Any(coin => coin <= 0)) throw new ArgumentException("Positive coins and nonnegative amount required");
int[] best = Enumerable.Repeat(amount + 1, amount + 1).ToArray(); best[0] = 0;
for (int sum = 1; sum <= amount; sum++) {
foreach (int coin in coins) if (coin <= sum) best[sum] = Math.Min(best[sum], best[sum - coin] + 1);
}
return best[amount] > amount ? -1 : best[amount];
}
Expected output
2 -1 0
A greedy largest-coin choice is not guaranteed optimal for arbitrary denominations.