> [!NOTE] Problem
> **Input**: The first input line has two integers $n$ and $x$: the number of coins and the desired sum of money. The second line has $n$ distinct integers $c_{1},\dots,c_{n}$: the value of each coins.
>
> **Output**: Print one integer: the minimum number of coins. If it is not possible to produce the desired sum, print $-1$.
>
>**Constraints:**
>- $1 \leq n \leq 100$
>- $1 \leq x \leq 10^{6}$
>- $1 \leq c_{i} \leq 10^{6}$
> Solution. Let $T(k)$ denote the minimum number of coins that produces the sum $k.$ Then $T(k) = \min(T(k-c_{1}), T(k-c_{2}),\dots,T(k-c_{n}))+1.$ Base case: $T(0)=0$ and for $k<0$, $T(k)=\infty.$
> Topological order is $k=1,\dots,x.$
> [!Example] Example
>**Input**:
>3 11
>1 5 7
>
>**Output**:
>3 since an optimal solution is $1+5+5$
Python implementation using [[Memoization|memoization]]:
```run-python
max_x = 10**6
inf = float('inf')
dp = [0]*(max_x)
# n, x = list(map(int, input().split()))
# c = list(map(int, input().split()))
n = 3; x = 11
c = [1,5,7]
for k in range (1, x+1):
dp[k] = inf
for i in range(n):
if (k-c[i] >= 0): dp[k] = min(dp[k-c[i]]+1, dp[k])
if dp[x] < inf:
print(dp[x])
else:
print(-1)
```