Minimum Number of Coins

You are given a list of coin denominations and a target sum. Your task is to determine the minimum number of coins required to form the target sum using the available denominations. If it is impossible to achieve the target sum, output -1.

Note: The problem utilizes dynamic programming to solve the classical coin change problem.

The formula to update the dynamic programming state is given by:

[ dp[t] = \min_{\text{coin}, \in, coins,, t \geq coin} (dp[t - coin] + 1) ]

with the base case \(dp[0] = 0\). If \(dp[target]\) remains \(\infty\), then the answer is \(-1\).

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer n representing the number of coin denominations.
• The second line contains n space-separated integers representing the coin denominations.
• The third line contains an integer target which is the target sum to form.

outputFormat

Output the minimum number of coins required to make the target sum. If it is not possible, output -1. The output should be printed to standard output (stdout).

3
1 2 5
11

3