Build an array dp where dp[i] stores the fewest coins needed to make amount i.

Coin Change

medium

Acceptance: 43%

Dynamic Programming

You have coins of various denominations available in unlimited supply. Determine the minimum number of coins required to reach a specified total. If the total cannot be assembled from the given denominations, return -1.

Examples

Example 1:

Input:coins = [1,3,4], amount = 6

Output:2

Explanation: 6 = 3 + 3, using two coins.

Example 2:

Input:coins = [5,7], amount = 3

Output:-1

Explanation: No combination of 5s and 7s can produce 3.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Coin Change

Examples

Hints

Related Problems