Coin Change Problem

You are given a list of coin denominations and an amount of money. Your task is to compute the minimum number of coins required to make up the given amount. If it is impossible to obtain exactly the given amount, output -1.

You can use as many coins of each denomination as you want. The problem can be formulated using dynamic programming. Let \(dp[x]\) be the minimum number of coins required to get a total of \(x\). Then the recurrence is given by:

\( dp[x] = \min_{\text{coin} \le x} \{dp[x - \text{coin}] + 1\} \)

If \(dp[\text{amount}]\) is not updated and remains \(\text{amount}+1\), then output \(-1\).

inputFormat

The first line contains an integer \(n\), representing the number of coin denominations.

The second line contains \(n\) space-separated integers, where the \(i\)-th integer denotes the value of a coin denomination.

The third line contains an integer \(\text{amount}\), the target amount to form using the coins.

outputFormat

Output a single integer: the minimum number of coins required to form the given amount, or \(-1\) if it is impossible.

3
1 2 5
11

3