Minimum Number of Runes

Problem Description

You are given a list of rune values and a target amount. Your task is to determine the minimum number of runes required to sum exactly to the given amount. If it is not possible to achieve the target sum using the given runes, then output -1.

You can solve this problem by using dynamic programming. Let \(dp[a]\) be the minimum number of runes needed to obtain the sum \(a\). The recurrence relation is:

\(dp[a] = \min_{r \in \text{runeValues} \text{ and } a \ge r} (dp[a - r] + 1)\)

with the base case \(dp[0] = 0\). If \(dp[amount]\) is not achievable (i.e. remains infinity), then output \(-1\).

inputFormat

The input is read from stdin and is in the following format:

• The first line contains an integer n representing the number of rune types.
• The second line contains n space-separated integers, which are the rune values.
• The third line contains an integer amount which is the target sum.

outputFormat

Output a single integer to stdout representing the minimum number of runes required to sum up to the given amount, or -1 if it is not possible.

1
1
0

0