Problem:
Coin Changing Problem Find the minimum number of coins to make change for n cents using coins of denominations d 1 , d 2 ,.., d m . The coins can be used any number of times. Input  n  m  d 1  d 2 ... d m  Two integers n and m are given in the first line. The available denominations are given in the second line. Output Print the minimum number of coins in a line. Constraints  1 ≤ n ≤ 50000  1 ≤ m ≤ 20  1 ≤ denomination ≤ 10000  The denominations are all different and contain 1.  Sample Input 1 55 4
1 5 10 50 Sample Output 1 2 Sample Input 2 15 6
1 2 7 8 12 50 Sample Output 2 2 Sample Input 3 65 6
1 2 7 8 12 50 Sample Output 3 3

Solution (Python):


INF = float('inf')

if __name__ == "__main__":
    N, M = list(map(int, input().split()))
    C = list(map(int, input().split()))
    dp = [INF for _ in range(N+1)]
    dp[0] = 0

    for i in range(M):
        c = C[i]
        for n in range(c, N+1):
            if dp[n-c] == INF:
                continue
            else:
                dp[n] = min(dp[n-c] + 1, dp[n])

    print(dp[N])

Solution (Python):
n,m=map(int,input().split())
c=list(map(int,input().split()))
dp=[[i for i in range(n+1)] for _ in range(m+1)]
for i in range(1,m+1):
    for w in range(1,n+1):
        if c[i-1]>w:
            dp[i][w]=dp[i-1][w]
        else:
            dp[i][w]=min(dp[i][w-c[i-1]]+1,dp[i-1][w])
print(dp[m][n])

Solution (Python):
n,m=map(int,input().split())
C=list(map(int,input().split()))

inf=float('inf')

DP=[[inf]*(n+1) for i in range(m+1)]

DP[0][0]=0

for i in range(m):
	for j in range(n+1):
		if j-C[i]<0:
			DP[i+1][j]=DP[i][j]
		else:
			DP[i+1][j]=min(DP[i][j],DP[i+1][j-C[i]]+1)

print(DP[m][n])

Solution (Python):
import sys
sys.setrecursionlimit(15000)
n,m = map(int,sys.stdin.readline().split())
M = list(map(int,sys.stdin.readline().split()))
dp = [float("inf")]*(n+1)
dp[0] = 0
for e in M:
  for i in range(n+1):
    if 0 <= i-e and i-e < n:
      dp[i] = min(dp[i],dp[i-e]+1)
print(dp[-1])

Solution (Python):
INF = 1145141919810364364334

n,m = map(int,input().split())
c = list(map(int,input().split()))
dp = [INF] * (n+1)
dp[0] = 0

for i in range(m):
    for j in range(n+1):
        if c[i] > j:
            continue
        else:
            dp[j] = min(dp[j] , dp[j-c[i]] + 1)
            
print(dp[n])

Solution (Python):
import sys
input = sys.stdin.readline


def inpl():
    return list(map(int, input().split()))


N, M = inpl()
coins = inpl()

dp = [i for i in range(N + 1)]
coins.sort()

for n in range(coins[1], N + 1):
    for c in coins[1:]:
        if c > n:
            continue
        dp[n] = min(dp[n], dp[n - c] + 1)


print(dp[N])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

from collections import deque
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n, m = na()
c = na()
dp = [[100000000] * (50001) for _ in range(20+1)]
for i in range(20+1):
    dp[i][0] = 0
for i in range(m):
    for j in range(n+1):
        if j >= c[i]:
            dp[i+1][j] = min(dp[i+1][j-c[i]] + 1, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[m][n])

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    c = list(map(int, input().split()))

    dp = [i+100 for i in range(N+1)]
    dp[0] = 0

    for i in range(1, N+1):
        for t in c:
            if i - t >= 0:
                dp[i] = min(dp[i], dp[i-t] + 1)
    
    print(dp[N])

if __name__ == "__main__":
    main()

Solution (Python):
N, M = map(int, input().split())
C = tuple(map(int, input().split()))

inf = 10**18
dp = [inf] * (N + 10)
dp[0] = 0

for c in C:
    for i in range(c, N + 1):
        dp[i] = min(dp[i], dp[i - c] + 1)
ans = dp[N]
print(ans)

Solution (Python):
n,m=map(int,input().split())
c=list(map(int,input().split()))

dp=[float('inf')]*(n+1)
dp[0]=0
for i in range(n+1):
    if dp[i]==float('inf'):continue
    for j in c:
        if i+j>n:continue
        dp[i+j]=min(dp[i]+1,dp[i+j])
print(dp[-1])

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
n,m=mi()
c = li()
dp=list(range(n+1))
for i in c:
    if(i==1):
        continue
    for j in range(i,n+1):
        dp[j] = min(dp[j], dp[j-i]+1)
print(dp[n])

Solution (Python):
N, M = map(int, input().split())
c = list(map(int, input().split()))

dp = [0] + [float('inf')] * N
for m in range(M):
    ci = c[m]
    for n in range(N + 1):
        if n - ci >= 0:
            dp[n] = min(dp[n], dp[n - ci] + 1)

print(dp[N])

Solution (Python):
n, m = map(int, input().split())
c = list(map(int, input().split()))

INF = 10**9
MAX = n + 1
dp = [INF for _ in range(MAX)]
dp[0] = 0
for i in range(m):
    for j in range(len(dp)):
        if j + c[i] < MAX:
            dp[j+c[i]] = min(dp[j] + 1, dp[j+c[i]])

min_v = dp[-1]
for i in range(len(dp)):
    idx = len(dp) - 1 - i
    min_v = min(min_v, dp[idx])
    dp[idx] = min_v

print(dp[n])

Solution (Python):
n, m = map(int, input().split())
C = list(map(int, input().split()))
dp = [-1] * (n+1)

for c in C:
    if c <= n:
        dp[c] = 1

for p in range(1, n+1):
    for c in C:
        if p-c < 0 or dp[p-c] < 0:
            continue
        dp[p] = min(dp[p], dp[p-c] + 1) if dp[p] > 0 else dp[p-c] + 1


print(dp[n])

Solution (Python):
def resolve():
    Nyens, Mtypes = map(int, input().split())  
    types = list(map(int, input().split()))  

    def knapsack(Nyens, Mtypes, types):
        
        
        dp = [[float('inf')] * (Nyens + 1) for _ in range(Mtypes + 1)]

        
        for ii in range(Mtypes):
            dp[ii][0] = 0

        for i in range(Mtypes):
            for j in range(Nyens + 1):
                if j >= types[i]:  
                    dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - types[i]] + 1)
                else:  
                    dp[i + 1][j] = dp[i][j]

        return dp[Mtypes][Nyens]

    print(knapsack(Nyens, Mtypes, types))

resolve()

Solution (Python):

n, m = map(int, input().split())


c = list(map(int, input().split()))

dp = [float("inf")] * (n + 1)
dp[0] = 0

for i in range(m):
    for j in range(n + 1):
        if dp[j] >= 0 and j + c[i] <= n:
            dp[j + c[i]] = min(dp[j + c[i]], dp[j] + 1)


print(dp[n])

Solution (Python):


s = input().split()
n = int(s[0])
m = int(s[1])

coins = input().split()


min_count = [99999 for i in range(n)]

for j in range(m):
    coins[j] = int(coins[j])
    
for i in range(n):
    buf = 99999
    if i+1 in coins:
        min_count[i] = 1
        continue
    for j in coins:
        if i<j: continue
        buf = min(buf,min_count[i-j]+1)
    min_count[i] = buf
    
print(min_count[n-1])

Solution (Python):
n, m = map(int, input().split())
coin = list(map(int, input().split()))
    


dp = [999999]*(n+1)
dp[0] = 0

for i in range(1, n+1):
    dp[i] = min([dp[i-coin[j]]+1 if i-coin[j]<n and i-coin[j]>=0 else 999999 for j in range(m)])

            
print(dp[n])

Solution (Python):
n, m = map(int, input().split())
C = sorted([int(x) for x in input().split()])
dp = [int(x) for x in range(n + 1)]
for c in C[1:]:
    for i in range(n + 1):
        anc = i - c
        if anc < 0:
            continue
        dp[i] = min(dp[i], dp[anc] + 1)
print(dp[n])

Solution (Python):
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

n, m = map(int, input().split())
c = list(map(int, input().split()))

dp = [[INF] * (n + 10) for _ in range(m + 10)]
for i in range(m+10):
    dp[i][0] = 0
for i in range(1, n + 1):
    if i % c[0] == 0:
        dp[1][i] = i // c[0]
for i in range(2, m + 1):
    for j in range(1, n + 1):
        if j - c[i - 1] >= 0:
            dp[i][j] = min(dp[i-1][j], dp[i][j - c[i - 1]] + 1)
        else:
            dp[i][j] = dp[i-1][j]
print(dp[m][n])

Solution (Python):
n, m = map(int, input().split())
c = list(map(int, input().split()))

dp = [float("inf")]*(n+1)
dp[0] = 0
for i in range(m):
    for j in range(c[i], n+1):
        dp[j] = min(dp[j], dp[j-c[i]]+1)
print(dp[n])

Solution (Python):
n,m=map(int,input().split())

c=list(map(int,input().split()))

cash=[0 for i in range(n+1)]

for i in range(1,n+1):
  for j in range(m):
    if (i-c[j])>=0:
      coins=cash[i-c[j]]+1
      if cash[i]==0:
        cash[i]=coins
      elif cash[i]>coins:
        cash[i]=coins

print(cash[n])

Solution (Python):
n, m = map(int, input().split())

c = list(map(int, input().split()))

dp = [[float('inf')]*(n+1) for _ in range(m+1)]
dp[0][0] = 0

for i in range(m):
    for j in range(n+1):
        if j - c[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i+1][j-c[i]] + 1)
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

print(dp[m][n])

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    c = LI()
    dp = [float("inf")]*(n+1)
    dp[0] = 0
    for i in range(m):
        ci = c[i]
        for j in range(n):
            nj = j+ci
            if nj <= n:
                nd = dp[j]+1
                if nd < dp[nj]:
                    dp[nj] = nd
    print(dp[n])
    return


if __name__ == "__main__":
    solve()

Solution (Python):
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

dp = [0] * (N + 1)

for i in range(1, N + 1):
    tmp = float("inf")
    for j in A:
        if i - j >= 0:
            tmp = min(tmp, dp[i - j])
    dp[i] = tmp + 1

print(dp[N])

Solution (Python):
N,M = map(int,input().split())
c = list(map(int,input().split()))
dp = list(range(N+1))
for i in range(N+1):
    for ci in c:
        if i + ci <= N:
            dp[i+ci] = min(dp[i+ci],dp[i] + 1)
print(dp[N])

Solution (Python):
if __name__ == '__main__':
    n, m = map(int, input().split())
    c = list(map(int, input().split()))

    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        for j in range(m):
            if i >= c[j]:
                dp[i] = min(dp[i - c[j]] + 1, dp[i])
    print(dp[n])

Solution (Python):
n,m = map(int,input().split(" "))
c = tuple(map(int,input().split(" ")))
m = min(c)
dp = [2**60 for _ in range(n+1)]
dp[0] = 0
for i in range(1,n+1):
    for v in c:
        if i >= v:
            dp[i] = min(dp[i],dp[i-v]+1)
print(dp[n])

Solution (Python):
n,m = map(int,input().split())
C = list(map(int,input().split()))

INF = 10**9

dp = [INF for _ in range(n+1)] 
dp[0] = 0
for i in range(m):
    if C[i] < n+1:
        dp[C[i]] = 1

for i in range(n+1):
    for j in range(m):
        if i-C[j] >= 0:
            dp[i] = min(dp[i],dp[i-C[j]] + 1)

print(dp[n])

Solution (Python):
inf = 10 ** 20
n,m = map(int,input().split())
c = [int(i) for i in input().split()]
dp = [inf for _ in range(n + 1)]
dp[0] = 0
for coin in c:
    for j in range(n + 1):
        if j - coin >= 0:
            dp[j] = min(dp[j], dp[j - coin] + 1)
print(dp[n])

Solution (Python):
n, m = map(int, input().split())
c = list(map(int, input().split()))

dp = [[10**8]*(n+1) for i in range(m+1)]
dp[0][0] = 0
for i in range(m):
    for j in range(n+1):
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        if j + c[i] <= n:
            dp[i+1][j+c[i]] = min(dp[i+1][j]+1, dp[i+1][j+c[i]])

print(dp[m][n])

Solution (Python):
import sys
input = sys.stdin.readline

n, m = map(int,input().split())
c = [0] + list(map(int,input().split()))

dp = [[0] + [n+1 for _ in range(n)] for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if j >=c[i]:
            dp[i][j] = min(dp[i-1][j],dp[i][j-c[i]]+1)
        else:
            dp[i][j] = dp[i-1][j]

print (dp[m][n])

Solution (Python):



N,M = map(int, input().split())
C = list(map(int, input().split()))

C.sort()
dp = [[float("inf") for _ in range(N+1)] for _ in range(M+1)]
dp[0][0] = 0



for i in range(M):
    for j in range(N+1):
        
        if C[i] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j - C[i]] + 1)

print(dp[-1][-1])

Solution (Python):
n, m = map(int, input().split())
c = list(map(int, input().split()))

dp = [float('inf') for _ in range(n + 10001)]
dp[0] = 0

for i in range(n):
    for j in c:
        dp[i + j] = min(dp[i + j], dp[i] + 1)

print(dp[n])

Solution (Python):
N, M = map(int, input().split())
C = [0] + list(map(int, input().split()))
C.sort()

dp = [[0] * (N+1) for _ in range(M+1)]
for i in range(N+1):
	dp[1][i] = i
for i in range(2,M+1):
	for j in range(1, N+1):
		if C[i] > j:
			dp[i][j] = dp[i-1][j]
		else:
			dp[i][j] = min(dp[i-1][j], dp[i][j-C[i]]+1)

print(dp[M][N])

Solution (Python):


N, M = list(map(int, input().split()))
C = list(map(int, input().split()))
T = [float('inf')] * (N+1)
T[0] = 0

for i in range(M):
    for j in range(C[i], N + 1):
        T[j] = min(T[j], T[j - C[i]] + 1)

print(T[-1])

Solution (Python):
a,b = [int(i) for i in input().split()]
l =  [int(i) for i in input().split()]
ans = [10**9 for _ in range(a+1)]       
ans[0] = 0          

for i in range(a+1):
    for j in l:
        if i + j < a+1:
            ans[i+j] = min(ans[i] + 1,ans[i+j])
            
print(ans[-1])

Solution (Python):
length, t = map(int, input().split(" "))
target = [int(n) for n in input().split(" ")]
dp = [float("inf") for n in range(length + 1)]
dp[0] = 0
for i, coin in enumerate(target):
    for j in range(length):
        if coin + j <= length:
            dp[coin + j] = min(dp[coin + j], dp[j] + 1)
print(dp[length])

Solution (Python):
N , M = map(int,input().split())
C = list(map(int,input().split()))

G = [[0]*(N+1) for _ in range(M+1)]

for i in range(N+1):
    G[0][i] = 1000000

for kinds in range(1,M+1):
    for kingaku in range(1,N+1):
        if kingaku-C[kinds-1]<0:
            G[kinds][kingaku] = G[kinds-1][kingaku]
            continue
        
        
        
        
        G[kinds][kingaku] = min(G[kinds-1][kingaku], G[kinds][kingaku-C[kinds-1]]+1)
        
        


print(G[M][N])

Solution (Python):
from itertools import product
n, m = map(int, input().split())
c = list(map(int, input().split()))
dp = [i for i in range(n+1)]
for j, k in product(range(1, m), range(1, n+1)):
    if 0 <= k - c[j]:
        dp[k] = min(dp[k], dp[k-c[j]] + 1)
print(dp[-1])

Solution (Python):
INF = 10**18

N,M = map(int,input().split())
C = list(map(int,input().split()))

dp = [INF for _ in range(N+1)]
dp[0] = 0

for i in range(M):
    for j in range(N+1):
        if j-C[i] >= 0:
            dp[j] = min(dp[j],dp[j-C[i]]+1)

print(dp[N])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline()[:-1]
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def MF(): return map(float, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LF(): return list(map(float, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
dij = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def main():
    inf=10**6
    n,m=MI()
    cc=LI()
    dp=[inf]*(n+1)
    dp[0]=0
    for c in cc:
        for i in range(n-c+1):
            if dp[i]==inf:continue
            if dp[i]+1<dp[i+c]:dp[i+c]=dp[i]+1
    print(dp[-1])

main()

Solution (Python):
n,m=[int(i) for i in input().split(" ")]
c=sorted([int(i) for i in input().split(" ")])
c.pop(0)
table=[[0 for j in range(n+1)] for i in range(m)]
for j in range(n+1):
    table[0][j]=j
for i in range(1,m):
    for j in range(n+1):
        if j>=c[i-1]:
            table[i][j]=min(table[i-1][j],table[i-1][j-c[i-1]]+1,table[i][j-c[i-1]]+1)
        else:
            table[i][j]=table[i-1][j]

print(table[-1][-1])

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

def resolve():
    n, m = iim()
    C = list(iim())

    dp = [n] * (n + 1)
    dp[0] = 0
    for co in C:
        for i in range(co, n+1):
            dp[i] = min(dp[i], dp[i-co] + 1)
    print(dp[n])

if __name__ == "__main__":
    resolve()

Solution (Python):
nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]

l = list(map(int, input().split()))

c = [[0] * (n+1) for i in range(m)]

count = 0
for i in range(1, n+1):
    count += 1
    c[0][i] = count


for i in range(1, m):
    loop = True
    count = 0
    
    for j in range(1, n+1):
        if j - l[i] >= 0:
            if c[i-1][j] > c[i][j-l[i]] + 1:
                c[i][j] = c[i][j-l[i]] + 1
            else:
                c[i][j] = c[i-1][j]
        else:
            c[i][j] = c[i-1][j]


print(c[-1][-1])

Solution (Python):
n,m = map(int, input().split())
coin = list(map(int,input().split()))
dp = [float("inf") for i in range(n+1)]
dp[0] = 0
for i in range(n+1):
    for j in coin:
        if i+j <= n:
            dp[i+j] = min(dp[i+j],dp[i]+1)

print(dp[n])

Solution (Python):


INF = 2000000000

def getTheNumberOfCoin():
    for i in range(n + 1):
        T.append(INF)
    T[0] = 0
    
    for i in range(m):
        for j in range(C[i], n + 1):
            T[j] = min(T[j], T[j-C[i]] + 1)
    
    return T




T = []
C = []
nums=list(map(int,input().split()))
n = nums[0]
m = nums[1]
nums=list(map(int,input().split()))
for i in range(m):
    C.append(nums[i])

getTheNumberOfCoin()
print(T[n])

Solution (Python):
n, m = map(int, input().split())
c = list(map(int, input().split()))
dp = [0]+[float("inf")]*n
for i in range(n): dp[i+1] = min([float("inf")]+[dp[i+1-c_j] for c_j in c if c_j<=i+1])+1
print(dp[-1])

Solution (Python):








INF = 1e5


n, m = list(map(int, input().split()))
C = list(map(int, input().split()))


dp = [[INF] * (n + 1) for _ in range(m)]  




for i in range(m):
    dp[i][0] = 0
for j in range(1 + n):
    dp[0][j] = j  






from itertools import product

for i, j in product(range(1, m), range(1, n + 1)):
    dp[i][j] = min(dp[i][j], dp[i - 1][j])
    if 0 <= j - C[i]:
        dp[i][j] = min(dp[i][j], dp[i][j - C[i]] + 1)

print(dp[i][j])

Solution (Python):
import sys

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def MAP(): return [int(s) for s in input().split()]

n,m=MAP()
a=MAP()



dp=[float('inf') for _ in range(n+1)]
dp[0]=0

for i in range(n+1):
	for j in a:
		if i+j <= n:
			dp[i+j]=min(dp[i]+1,dp[i+j])

print(dp[-1])

Solution (Python):
def get_number_of_coin(coins, dp_coin, total):
    for c in coins:
        for j in range(c, total + 1):
            dp_coin[j] = min(dp_coin[j], dp_coin[j - c] + 1)
    return dp_coin[-1]


if __name__ == "__main__":
    total, n_coin = map(int, input().split())
    *coins, = map(int, input().split())    
    dp_coin = [10000] * (total + 1)
    dp_coin[0] = 0
    print(get_number_of_coin(coins, dp_coin, total))

Solution (Python):
INF = 10**10
N,M = map(int,input().split())
Coins = list(map(int,input().split()))
Coins.sort()




DP = [ [INF]*(N+1) for _ in range(M+1) ]


for i in range(1,M+1):
    DP[i][0] = 0


for i in range(1,N+1):
    DP[1][i] = i

for m in range(2,M+1):
    for n in range(1,N+1):
        
        
        c = Coins[m-1]
        if n >= c:
            DP[m][n] = min(DP[m][n],DP[m][n-c] + 1)
        DP[m][n] = min(DP[m][n],DP[m-1][n])

print(DP[M][N])

Solution (Python):
n,m = map(int,input().split())
c = list(map(int,input().split()))
i = 0
dp = [0] * 50001
for i in range(50001):
    dp[i] = i

for i in range(2,n+1):
    for j in range(m):
        if i - c[j] >= 0:
            dp[i] = min(dp[i], dp[i - c[j]] + 1)

print(dp[n])

Solution (Python):
n,m=map(int,input().split())
c=list(map(int,input().split()))
c.sort()

dp=[[0 for j in range(n+1)] for i in range(m)] 
for j in range(n+1):
    dp[0][j]=j
for i in range(1,m):
    for j in range(n+1):
        if j<c[i]:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][j-c[i]]+1)
    
print(dp[m-1][n])

Solution (Python):

inf = float("inf")
N,M = map(int,input().split())
C = list(map(int,input().split()))
C.sort()

dp = [inf for i in range(N+1)]
dp[0] = 0
for c in C:
    for p in range(c,N+1):
        dp[p] = min(dp[p],dp[p-c]+1)
        
print(dp[N])

Solution (Python):

import sys, math
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans=count=0

n,m=map(int,input().split())
A=list(map(int,input().split()))
dp=[inf]*(n+1)
dp[0]=0
for a in A:
    for i in range(a,n+1):
        dp[i]=min(dp[i],dp[i-a]+1)
print(dp[n])

Solution (Python):
n,m=map(int,input().split())
coins=list(map(int,input().split()))
DP = [n for i in range(n + 1)]
DP[0]=0
for c in coins:
    for i in range(c, n + 1):
        DP[i] = min(DP[i], DP[i - c] + 1)
print(DP[n])

Solution (Python):
def main():
    n, m = map(int, input().split())
    mo = list(map(int, input().split()))
    dp = [float("inf") for i in range(n + 2)]
    dp[0] = 0
    for i in range(n + 1):
        for j in mo:
            if i + j <= n:
                temp_index = i + j
                dp[temp_index] = min(dp[temp_index], dp[i] + 1)
    print(dp[n])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
n , m = map(int,input().split())
coins = list(map(int,input().split()))
coins.sort(reverse=True)
dp = [[float("inf")]*(n + 1) for _ in range(m + 1)]
def solve(i , value):
    if dp[i][value] != float("inf"):
        return dp[i][value]
    if i == m - 1 or value == 0:
        ret_val = value
    elif coins[i] > value:
        ret_val = solve(i + 1,value)
    else:
        ret_val = min(solve(i + 1,value) , solve(i,value - coins[i]) + 1)
    dp[i][value] = ret_val
    return ret_val

solve(0 , n)
print(dp[0][n])

Solution (Python):
n,m = map(int,input().split())
coins = list(map(int,input().split()))


dp = [50001 for _ in range(50001)]
dp[0] = 0

for i in range(0,50001):
    for j in range(m):
        if i+coins[j] <= n:
            dp[i+coins[j]] = min(dp[i+coins[j]],dp[i]+1)
            
print(dp[n])

Solution (Python):
def main():
    n, m = map(int, input().split())
    
    INF = float('inf')
    dp = [[INF for i in range(n+1)] for j in range(m+1)]
    
    for i, c in enumerate(list(map(int, input().split()))):
        i += 1
        for j in range(1, n+1):
            if c == j:
                dp[i][j] = 1
            else:
                dp[i][j] = min(dp[i][j], dp[i-1][j])
                if j - c >= 0: dp[i][j] = min(dp[i][j], dp[i][j-c]+1)
    print(dp[-1][-1])

if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
c = list(map(int, input().split()))
dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(n):
    for j in range(m):
        if i + c[j] <= n:
            dp[i + c[j]] = min(dp[i + c[j]], dp[i] + 1)
print(dp[n])

Solution (Python):
n,m=map(int,input().split())
a=[i for i in range(n+1)]
for i in list(map(int,input().split())):
    for j in range(i,n+1):
        a[j]=min(a[j-i]+1,a[j])
print(a[-1])

Solution (Python):
from collections import deque

def min_coin_select(C, m, n):
    DP = [float('inf')] * (n+1)
    DP[0] = 0
    
    C.appendleft(0)

    for i in range(1, m+1):
        for j in range(1, n+1):
            if j >= C[i]:
                DP[j] = min(DP[j-C[i]] + 1, DP[j])

    return DP[n]

def read_and_print_results():
    n, m = [int(i) for i in input().split()]
    C = deque([int(i) for i in input().split()])
    print(min_coin_select(C, m, n))

read_and_print_results()

Solution (Python):
n,m,*L=map(int,open(0).read().split())
dp=list(range(n+1))
for c in L:
	for j in range(c,n+1):
		dp[j]=min(dp[j],dp[j-c]+1)
print(dp[n])

Solution (Python):
N, M = map(int, input().split())
C = list(map(int, input().split()))
C = [0] + C

MAX = 10_001
dp = [MAX for i in range(N+1)]
dp[0] = 0

for i in range(1, M+1):
  for j in range(C[i], N+1):
    dp[j] = min(dp[j], dp[j-C[i]]+1)

print(dp[N])

Solution (Python):



import itertools as ite
import math
import random
import sys
import codecs
from collections import defaultdict

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

n, m = map(int, input().split())
c = list(map(int, input().split()))
DP = [0] + [n] * n
for i in range(m):
    for j in range(c[i], n + 1):
        DP[j] = min(DP[j], DP[j - c[i]] + 1)
print(DP[n])

Solution (Python):
n, m = map(int, input().split())
c_list = list(map(int, input().split()))
c_list.sort()
dp_list = [0] + [10**9]*(n)
for i in range(1, n+1):
    for c in c_list:
        if i - c >= 0:
            dp_list[i] = min(dp_list[i], dp_list[i-c]+1)
        else:
            break
print(dp_list[-1])

Solution (Python):
n,m=map(int,input().split())
x=list(map(int,input().split()))

memo=[n+1 for _ in range(n+1)]
memo[n]=0

for i in range(n,-1,-1):
    for xx in x:
        if i-xx<0:
            continue
        memo[i-xx]=min(memo[i-xx],memo[i]+1)
print(memo[0])

Solution (Python):
import sys


if __name__ == "__main__":
    n, m = map(lambda x: int(x), input().split())
    coins = list(map(lambda x: int(x), input().split()))

    table = [sys.maxsize] * (n + 2)
    table[0] = 0
    for i in range(n + 1):
        for coin in coins:
            if (i + coin <= n):
                table[i + coin] = min(table[i + coin], table[i] + 1)

    print(table[n])

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
memory = [10**6 for _ in range(N + 1)]
flg = [False for _ in range(N + 1)]
memory[0] = 0
flg[0] = True
for a in A:
  m = 0
  while m < len(memory) and m + a < len(memory):
    if flg:
      memory[m + a] = min(memory[m] + 1, memory[m + a])
      flg[m + a] = True
    m += 1
print(memory[-1])

Solution (Python):
n, m = map(int, input().split())
d = list(map(int, input().split()))

T = [50001]*(n+1)
T[0] = 0
for i in range(m):
    for j in range(d[i],n+1):
        T[j] = min(T[j], T[j-d[i]]+1)
print(T[n])

Solution (Python):
from typing import List


def changes(amount: int, kind: int, coins: List[int]) -> int:

    T: List[int] = [50001] * (amount + 1)
    T[0] = 0

    for i in range(kind):
        for j in range(coins[i], amount + 1):
            T[j] = min(T[j], T[j - coins[i]] + 1)

    return T[amount]


def main() -> None:
    n, m = [int(x) for x in input().split()]
    c = [int(x) for x in input().split()]

    print(changes(n, m, c))


main()

Solution (Python):


def solve():
    INF = 1e+9
    n, m = map(int, input().split())
    c = list(map(int, input().split()))

    dp = [[0]*(n+1) for _ in range(m+1)]
    for j in range(n+1):
        dp[0][j] = INF

    for i in range(1, m+1):
        for j in range(1, n+1):
            jj = j - c[i-1]
            if jj < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i][jj] + 1)

    print(dp[-1][-1])


if __name__ == "__main__":
    solve()

Solution (Python):
I=input().split( )
n=int(I[0])
m=int(I[1])

C=input().split( )
c=[int(C[i]) for i in range(m)]

T=[50001 for i in range(n+1)]
T[0]=0

for i in range(m):
    for j in range(n+1):
        if c[i]+j<=n:
            T[j+c[i]]=min(T[j+c[i]],T[j]+1)

print(T[n])

Solution (Python):
n, m = map(int, input().split())
c = list(map(int, input().split()))
dp = [[0],[i for i in range(n+1)]]
for mi in range(1, m):
    dp.append([0])
    coin = c[mi]
    for ni in range(1, n+1):
        if ni>=coin:
            dp[-1].append(min(dp[-1][-c[mi]]+1,dp[-2][ni]))
        else:
            dp[-1].append(dp[-2][ni])
print(dp[-1][n])

Solution (Python):

import string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    
    n, m = readi(2)
    coins = readi(m)
    dp = arr(n + 1, fill_value=INF)
    dp[0] = 0
    for i in range(n):
        for c in coins:
            if i + 1 - c >= 0:
                dp[i + 1] = min(dp[i + 1], dp[i + 1 - c] + 1)
    print(dp[n])


if __name__ == "__main__":
    main()

Solution (Python):
inf = float('inf')

n,m = map(int,input().split())
c = list(map(int,input().split()))

dp = [inf]*(n+1)
dp[0] = 0
for i in range(1,n+1):
    for ci in c:
        if i - ci >= 0:
            dp[i] = min(dp[i], dp[i-ci] + 1)

ans = dp[n]
print(ans)

Solution (Python):
n,m=map(int,input().split())
C=set(map(int,input().split()))

ANSLIST=[n]*(n+1)

ANSLIST[0]=0

for i in range(1,n+1):
    ANSLIST[i]=min([ANSLIST[i-c]+1  for c in C if i-c>=0])

print(ANSLIST[n])

Solution (Python):
n, m = map(int, input().split())
c = [int(i) for i in input().split()]
dp = [5*10**4]*(n+1)

dp[0] = 0
for i in range(1,n+1):
  dp[i] = min([dp[i-j]+1 for j in c if i>=j])
print(dp[n])

Solution (Python):
import os
from functools import lru_cache

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))


@lru_cache(maxsize=None)
def solve(n):
    if n == 0:
        return 0
    if n < 0:
        return IINF
    ret = IINF
    for c in C:
        ret = min(ret, solve(n - c) + 1)
    return ret


print(solve(N))

Solution (Python):
n,m=map(int,input().split())
c=list(map(int,input().split()))

dp=[[float('inf')]*(n+1) for _ in range(m+1)]
dp[0][0]=0
for i in range(m):
    for j in range(n+1):
        if j-c[i]>=0:
            dp[i+1][j]=dp[i+1][j-c[i]]+1
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])

print(dp[-1][-1])

Solution (Python):
def smaller(x, y):
	if x < y: return x
	return y

N, M = map(int, input().split())
coins = list(map(int, input().split()))
dp = []
for i in range(0, N+1):
	dp.append(100000)
dp[0] = 0
for i in range(0, N):
	for j in range(0, M):
		if i+coins[j] <= N:
			dp[i+coins[j]] = smaller(dp[i]+1, dp[i+coins[j]])
print(dp[N])