Coin Change
Coin Change
You are given an array of coin denominations (you have infinite supply of each) and a target amount. Find the minimum number of coins needed to make up exactly that amount. If it is impossible to reach the target with the given coins, print -1. Your solve(...) function receives these inputs directly as ready-made arguments — no input reading or parsing needed. Just compute and return the answer. Example: n=3, amount=11, coins=[1 5 6] → 2 (use 5+6)
Input format — only if your code reads from stdin
Input format (stdin): - First line: two integers n (number of coin types) and amount (the target) - Second line: n space-separated coin denominations Output: the minimum number of coins, or -1 if the amount cannot be made.
Approach
Bottom-up DP: create dp[0..amount] where dp[i] = min coins to make amount i. Initialize dp[0]=0, rest=Infinity. For each amount i from 1 to amount, try every coin c ≤ i: dp[i] = min(dp[i], dp[i-c]+1). Answer is dp[amount] or -1 if still Infinity.
Input
Output
- •
1 ≤ n ≤ 12, 1 ≤ amount ≤ 10^4, 1 ≤ coin[i] ≤ 1000
More Dynamic Programming problems
Browse all coding problems →Press Run to test your custom input, or Submit to judge against all test cases.
Sign in to continue
Create a free account to run code, submit solutions and track progress.
- Free forever — no credit card
- 10+ languages with live execution
- Points, streaks & leaderboards