Coin Change Dynamic Programming | Dataford Interview Questions

Tekion payment workflows may support a fixed set of coin denominations for handling a cash amount. Given the available denominations and a target amount, return the minimum number of coins needed to make that amount. Each denomination may be used unlimited times. If the amount cannot be formed, return -1.

Formal Specification

Implement coin_change(coins, amount):

coins is a list of positive integers representing available denominations.
amount is a non-negative integer representing the target amount.
Return an integer containing the fewest coins needed to total exactly amount, or -1 when no combination is possible.
The order of coins does not matter.

Constraints

1 <= len(coins) <= 12
1 <= coins[i] <= 10^4
0 <= amount <= 10^4
Duplicate denominations may appear in coins

Function Signature

def coin_change(coins, amount):

Your question is Coin Change Dynamic Programming. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem