Coin Change in Java: Explanation & Practice

Minimum coins needed to make amount

Problem summary

Given coin denominations and a target amount, find the minimum number of coins needed to make that amount. Return -1 if impossible.

Starter code

public class Main {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        
        // dp[i] = min coins needed for amount i
        // dp[i] = min(dp[i], dp[i-coin] + 1) for each coin
        // Print: Min coins: 3
    }
}

Expected output and test cases

[1,2,5], amount=11 → 5+5+1
```
Min coins: 3
```
[2], amount=3 → impossible
```
Min coins: -1
```
[1], amount=0 → 0 coins
```
Min coins: 0
```

Hints

Create dp array of size amount+1, initialize with infinity
dp[0] = 0 (0 coins needed for amount 0)
For each amount i, try each coin: dp[i] = min(dp[i], dp[i-coin]+1)
Only consider coin if i >= coin value

Related Data Structures & Algorithms exercises

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler