MemotivaLeetCode Patterns Flashcards: Dynamic Programming, Memoization, Tabulation, Patterns

How does the coin change problem use DP?

Nortren·

How does the coin change problem use DP?

0:28

Given coin denominations and a target amount, find the minimum number of coins needed to make the target. The state is the remaining amount. For each amount from one to the target, try every coin denomination and take the minimum result. The transition is: dp at amount equals one plus the minimum of dp at amount minus coin value, for all coins whose value does not exceed the current amount. The base case is dp at zero equals zero. Amounts that cannot be formed keep their initial value of infinity. This runs in O of amount times number of coins.
neetcode.io