1D DP Recurrence with a Sentinel

core

Implement min_coins(n, coins), returning an array dp of length n + 1 where dp[a] is the fewest coins from coins that sum to exactly a, or -1 when no combination reaches a. Every coin value is a positive integer and may be used any number of times; coins may repeat a value or hold values larger than n. dp[0] is always 0, since the empty selection sums to zero.

Build it bottom-up rather than recursively, in three parts: fill the whole table with a sentinel meaning "not reachable yet", set the one base cell dp[0] = 0, and for each amount a from 1 to n and each coin c with a >= c, take dp[a - c] + 1 as a candidate for dp[a]. Two properties of the sentinel decide whether that works. It must be a value no real answer can take: a table you allocate without an explicit fill starts at 0, and 0 is a legal coin count, so every min settles on it immediately and the whole table comes back zero. And it must leave headroom above it, because a sentinel pinned to the type's maximum overflows the moment you add 1; keeping the reach guard "dp[a - c] is not the sentinel" means you never do that arithmetic in the first place. An amount needs at most n coins, so anything comfortably above n is a safe sentinel. Translate it back to -1 only when you build the returned array.

Example: min_coins(10, {3, 5}) returns {0, -1, -1, 1, -1, 1, 2, -1, 2, 3, 2}. Amount 6 is 3 + 3, amount 8 is 3 + 5, amount 9 is 3 + 3 + 3, and amount 10 is 5 + 5; amounts 1, 2, 4 and 7 cannot be formed at all, so they stay -1.

Input format: each test in tests/*.in is laid out as:

Line 1: n k, the target amount and the number of coins.
Line 2: the k coin values, space-separated.

Test 03.in reads:

0 1
2

This is the edge case that looks strangest raw: n = 0 with k = 1 coin of value 2. Line 2 is the whole coin list, so the returned table is just {dp[0]} = {0}.

Where you'll use it:

✦ Solution & editorial unlock with the pass.