Coin change (DP)
mediumdp[a] is the fewest coins that make a. Every entry depends only on smaller amounts, so a single left-to-right pass is enough - and unlike greedy, it is always right.
Worst
O(amount × coins)Space O(amount)Loading the coin change (dp) engine…