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):
n, m = list(map(int, input().split(' ')))
c = list(map(int, input().split(' ')))

table = [[0 for j in range(n+1)] for i in range(m+1)]
table[0][1:] = [float('inf') for j in range(1, n+1)]
for i in range(1, m+1):
    for j in range(1, n+1):
        if j - c[i-1] < 0:
            table[i][j] = table[i-1][j]
        else:
            table[i][j] = min(table[i-1][j], table[i][j-c[i-1]]+1)

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

Solution (Python):

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

Solution (Python):

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

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

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

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

print(a[n])

Solution (Python):

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

Solution (Python):

import sys
sys.setrecursionlimit(100000000)

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


def func(num, yen):
	if num < 0 or yen < 0:
		return 10 ** 18
	if num == 0 and yen == 0:
		return 0
	if not (num, yen) in DP:
		DP[(num, yen)] = min(func(num - 1, yen), func(num, yen - c[num]) + 1)
	return DP[(num, yen)]

print(func(m - 1, n))

Solution (Python):
INF = 10 ** 20

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

dp = [INF for _ in range(n + 1)]
dp[0] = 0
for coin in c_lst:
  for price in range(coin, n + 1):
    dp[price] = min(dp[price], dp[price - coin] + 1)

print(dp[n])

Solution (Python):
N,M = map(int,input().split())
coins = list(map(int,input().split()))
coins.sort()
dp = [[0] * M for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = i
for j in range(M):
    dp[0][j] = 0
for j in range(1,M):
    for i in range(1,N+1):
        if coins[j] <= i:
            dp[i][j] = min(dp[i-coins[j]][j]+1,dp[i][j-1])     
        else:
            dp[i][j] = dp[i][j-1]
        
print(dp[N][M-1])

Solution (Python):
n,m = map(int, input().split())
mo = 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 mo:
        if i+j <= n:
            dp[i+j] = min(dp[i+j],dp[i]+1)
print(dp[n])

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

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

Solution (Python):
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:
            dp[i+j] = min(dp[i+j],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') for _ in range(n+1)]
    dp[0] = 0
    for i in range(n+1):
        for j in range(m):
            if i - c[j] >= 0:
                dp[i] = min(dp[i-c[j]]+1, dp[i])

print(dp[n])

Solution (Python):
def main():
    N, M = map(int, input().split())
    C = list(map(int, input().split()))
    dp = [float('inf')] * (N + 5)
    dp[0] = 0
    for i in range(N+1):
        for c in C:
            if i + c > N + 1:
                continue
            dp[i+c] = min(dp[i+c], dp[i] + 1)

    print(dp[N])


if __name__ == "__main__":
    main()

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

C.sort()
DP = [i for i in range(N+1)]

for m in range(1,M):
    coin = C[m]
    for total in range(1, N+1):
        if total - coin >= 0:
            DP[total] = min(DP[total], DP[total - coin] + 1)

print(DP[-1])

Solution (Python):


N, M = map(int, input().split())
C_L = [int(x) for x in input().split()]


dp = [float("Inf")] * (N+1)
dp[0] = 0
for i in range(1, N+1):
    for j in range(M):
        _c = C_L[j]
        if i >= _c:
            dp[i] = min(dp[i-_c] + 1, dp[i])

print(dp[N])

Solution (Python):
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readlines
infty = 2 ** 20

lines = input()

n, m = list(map(int, lines[0].split()))

coin = list(map(int, lines[1].split()))

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


for i in range(1, n+1):
    T[0][i] = infty

for i in range(m+1):
    T[i][0] = 0

for i in range(1, n+1):
    T[1][i] = i

cnt = 0
for i in range(1, m+1):
    if coin[i-1] > n:
        continue
    else:
        cnt += 1
        for j in range(1, n+1):
            if j < coin[i-1]:
                T[i][j] = T[i-1][j]
            else:
                a = T[i-1][j] ; b = T[i][j-coin[i-1]]+1
                if a < b:
                    T[i][j] = a
                else:
                    T[i][j] = b

print(T[cnt][n])

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

dp = [[10**18]*(N+10) for _ in range(M+10)]
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][j - C[i]] + 1, dp[i][j], dp[i+1][j - C[i]] + 1)
        else:
            dp[i+1][j] = dp[i][j]



print(dp[M][N])

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


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

for _ in range(m+1):
    dp[_][0] = 0

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

Solution (Python):

n, m = list(map(int, input().split(" ")))
c = list(map(int, input().split(" ")))
dp = [10**5 for i in range(n + 1)]
dp[0] = 0

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

Solution (Python):
n, m = map(int, input().split())
coins = list(map(int, input().split()))
coins = sorted(coins, reverse=False)
dp = [[float('inf')] * (n + 1) for _ in range(m)]

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

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

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

Solution (Python):
N, M = map(int, input().split())
C = [int(x) for x in input().split()]
C.sort()
A = [0 for _ in range(N + 1)]
for c in C:
    if c > N:
        break
    A[c] = 1
for i in range(1, N + 1):
    pos = []
    for c in C:
        if i - c < 0:
            break
        pos.append(A[i - c])
    A[i] = min(pos) + 1
print(A[-1])

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    C = list(map(int, input().split()))

    INF = 10 ** 18
    dp = [INF] * (N + 1)
    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[-1]
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    n, m = MI()
    mlist = LI()
    d = [[float('inf') if i != 0 else 0 for i in range(n+1)] for j in range(m+1)]
    for i, value in enumerate(mlist):
        for j in range(n+1):
            if j < value:
                d[i+1][j] = d[i][j]
            else:
                d[i+1][j] = min(d[i][j], d[i+1][j-value]+1)
    print(d[m][n])

        
    
if __name__ == "__main__":
    main()

Solution (Python):
n,m=map(int,input().split())
c=sorted(list(map(int,input().split())))
dp=[10**18]*(n+1)
for i in c:
  if i>n:break
  dp[i]=1
  for j in range(i+1,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 = [None]*50001
for i in c:
    dp[i] = 1

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

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

coins = map(int, input().split())

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

for coin in coins:
    for index in range(N-coin+1):
        dp[index+coin] = min(dp[index+coin], dp[index]+1)
print(dp[N])

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

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

dp = [20**10]*(n+1)
dp[0] = 0
for coin in coins:
    for price in range(coin,n+1):
        dp[price]  = min(dp[price],dp[price-coin]+1)
        
print(dp[n])

Solution (Python):
charge, n_coin = map(int,input().split())
coin_ls = list(map(int, input().split()))
coin_ls = [0] + coin_ls

dp = [[float('inf')] * (charge+1) for _ in range(n_coin+1)]
dp[0][0] = 0
for coin_i in range(1,n_coin+1):
    for now_charge in range(0,charge+1):
        if now_charge - coin_ls[coin_i] >= 0:
            dp[coin_i][now_charge] = min(dp[coin_i][now_charge], dp[coin_i][now_charge-coin_ls[coin_i]]+1)
        dp[coin_i][now_charge] = min(dp[coin_i-1][now_charge], dp[coin_i][now_charge]) 
print(dp[n_coin][charge])

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):
N, M = map(int, input().split())
C = list(map(int, input().split()))
INF = 10**9
dp = [INF]*(N+1)
dp[0] = 0
for i in range(M):
    for n in range(N+1):
        if n >= C[i]:
            dp[n] = min(dp[n], dp[n-C[i]]+1)
print(dp[N])

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

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

dp[0]= 0

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

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N, M = map(int, readline().split())
    C = list(map(int, readline().split()))
    
    dp = [INF] * (N+1)
    dp[0] = 0
    for c in C:
        if c<=N:
            for i in range(N-c+1):
                dp[i+c] = min(dp[i]+1, dp[i+c])
    print(dp[N])


if __name__ == '__main__':
    main()

Solution (Python):
def coin(larger=False, single=False):
    """
    ナップサックに入れる重さが W 丁度になる時の価値の最小値
    :param single: True = 重複なし

    dp[weight <= W+1] = 重さを固定した時の最小価値
    dp[W+1] = 重さがWより大きい時の最小価値
    """
    W2 = W + 1              
    dp_max = float("inf")   
    dp = [dp_max] * (W2 + 1)
    dp[0] = 0               

    for item in range(N):
        if single:
            S = range(W2, weight_list[item] - 1, -1)
        else:
            S = range(W2)
        for weight in S:
            dp[min2(weight + weight_list[item], W2)] = min2(dp[min2(weight + weight_list[item], W2)], dp[weight] + cost_list[item])
    if larger:
        return min(dp[w] for w in range(W, W2+1))
    else:
        return dp[W]


import sys
input = sys.stdin.readline


def max2(x, y):
    return x if x > y else y

def min2(x, y):
    return x if x < y else y

W, N = map(int, input().split())                                









cost_list = [1]*N
weight_list = list(map(int, input().split()))

print(coin(single=False))

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(1, n + 1):
    for j in range(m):
        if i >= c[j]:
            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()))
INF = 10**5
dp = [INF for _ in range(n+1)]
dp[0] = 0
for i in range(n):
    for c in C:
        if i + c <= n:
            dp[i+c] = min(dp[i+c], dp[i]+1)
print(dp[n])

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

dp[0] = [i  for i in range(n+1)]
for i in range(1, m):
    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-1][n])

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

dp = [[0]*len(C) for n in range(N+1)] 

for n in range(1,N+1):
    dp[n][0] = n
    
for n in range(1,N+1):
    for c in range(1,len(C)):
        if C[c] > n:
            dp[n][c]=dp[n][c-1]
        else:
            dp[n][c]=min(dp[n][c-1],dp[n-C[c]][c]+1)
            
print(dp[-1][-1])

Solution (Python):
n,m=map(int,input().split())
c=list(map(int,input().split()))
dp=[10**5 for i in range(50001)]
dp[0]=0
dp[1]=1
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 = list(map(int, input().split()))

dp = [0] + [float('inf')] * N

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

Solution (Python):
from pprint import pprint
n,m=map(int,input().split())
c=list(map(int,input().split()))
dp=[[10**5]*(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][j-c[i]]+1,dp[i+1][j-c[i]]+1)

print(dp[m][n])

Solution (Python):
import sys


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    c = [0] + list(map(int, input().split()))
    dp = [list(range(n + 1)) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(n + 1):
            if j - c[i] >= 0:
                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])


if __name__ == "__main__":
    main()

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

dp=[[float("inf") for i in range(n+1)] for j in range(m+1)]

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

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

print(int(dp[m][n]))

Solution (Python):
cap, m = map(int, input().split())
arr = list(map(int, input().split()))

INF = 1 << 60
dp = [INF] * (cap + 1)
dp[0] = 0

for x in arr:
    for i in range(x, cap + 1):
        dp[i] = min(dp[i], dp[i - x] + 1)

print(dp[cap])

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

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

for coin in C:
    for pay in range(N+1):
        if pay-coin>=0:
            DP[pay]=min(DP[pay],DP[pay-coin]+1)

print(DP[-1])

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

def main():
    n, m = list(map(int, input().strip().split()))
    c = [0] + sorted(list(map(int, input().strip().split())))
    dp = [[0] * (n+1) for _ in range(m+1)]
    dp[0] = [INF] * (n+1)
    dp[0][0] = 0
    for i in range(1, m+1):
        for j in range(n+1):
            if j-c[i] < 0:
                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])

if __name__ == '__main__':
    main()

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


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





def main():
    n, m = ns()
    c = na()

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

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

    print(dp[n])


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

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


if __name__ == '__main__':
    resolve()

Solution (Python):
N,M = map(int,input().split())
C = list(map(int,input().split()))
INF = float('inf')
dp = [INF] * (N+1)
dp[0] = 0
for i in range(M):
  c = C[i]
  for j in range(N+1):
    if j >= c:
      dp[j] = min(dp[j], dp[j-c]+1)

print(dp[N])

Solution (Python):
cost,m,=map(int,input().split())
c=list(map(int,input().split()))
DP=[[10**10 for i in range(60001)] for j in range(21)]
for i in range(m):
    DP[i][c[i]]=1
    for j in range(60001):
        if c[i]>j:
            if i==0:
                DP[i][j]=0
            else:DP[i][j]=DP[i-1][j]
        elif j+c[i]<=60000:
            DP[i][j]=min(DP[i][j-c[i]]+1,DP[i-1][j])
print(DP[m-1][cost])

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

dp = [float('inf')]*10**5

dp[0] = 0

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

Solution (Python):
n,m=map(int,input().split())
c=list(map(int,input().split()))
dp=[[n]*(n+1) for _ in range(m+1)]
dp[0][0]=0
for i in range(1,m+1):
    for j in range(n+1):
        if j>=c[i-1]:
            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()))
INF = float('inf')
dp =[0] + [INF for _ in range(n)]



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)
        pass
    
print(dp[n])

Solution (Python):
INF = 10 ** 20

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

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

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

dp[0] = 0

for coin in lst:
    for j in range(coin, n+1):
        dp[j] = min(dp[j], dp[j-coin]+1)
print(dp[n])

Solution (Python):
n, m = map(int, input().split())
c = [int(i) for i in input().split()]
inf = 10**10

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]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-c[i]]+1, dp[i+1][j-c[i]]+1)
        else:
            dp[i+1][j] = dp[i][j]

print(dp[m][n])

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

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

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

print(dp[m][n])

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

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

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

for c in C:
    for i in range(n+1):
        if i+c > n:
            break
        dp[i+c] = min(dp[i+c], dp[i] + 1)

print(dp[n])

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

INF = 5 * 10 ** 4
dp = [[INF] * (n + 1) for _ in range(m + 1)]
dp[0][0] = 0
for i in range(1, m + 1):
    for j in range(n + 1):
        if j >= c[i - 1]:
            dp[i][j] = min(
                dp[i - 1][j], dp[i - 1][j - c[i - 1]] + 1, 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()))

INF = 5 * 10 ** 4
dp = [[INF] * (n + 1) for _ in range(m + 1)]
dp[0][0] = 0
for i in range(1, m + 1):
    for j in range(n + 1):
        if j >= c[i - 1]:
            dp[i][j] = min(
                dp[i - 1][j], dp[i - 1][j - c[i - 1]] + 1, 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()))

INF = 10**8
dp = [INF]*(N+1)
dp[0] = 0

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

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

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

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

print(dp[M][N])

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

MAX = 10 ** 5
dp = [MAX] * (n + 1)

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

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

dp = [50001] * (N + 1)
dp[0] = 0

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

print(dp[-1])

Solution (Python):
import sys

if __name__ == "__main__":
    n,m = map(int,input().split())
    c = list(map(int,input().split()))
    INF = 10**18
    dp = [INF]*(n+1)
    dp[0] = 0
    for i in c:
        for j in range(i,n+1):
            dp[j] = min(dp[j],dp[j-i]+1)
    print(dp[-1])

Solution (Python):
import sys
readline = sys.stdin.readline
INF = 10 ** 10


def main():
    N, M = map(int, readline().rstrip().split())
    C = list(map(int, readline().rstrip().split()))
    dp = [INF] * (N + 1)
    dp[0] = 0
    for c in C:
        for i in range(c, N+1):
            dp[i] = min(dp[i], dp[i-c] + 1)
    
    print(dp[N])


if __name__ == '__main__':
    main()

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

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

inf = float("inf")
dp = [inf for _ in range(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])
        else:
            dp[i] = dp[i]


print(dp[n])

Solution (Python):
W,N = map(int,input().split())
 
table = [10000000]*(W+1)
 
table[0] = 0
 
coin_list = list(map(int,input().split()))
 
for coin in coin_list:
    for i in range(coin,W+1):
        table[i] = min(table[i],table[i-coin]+1)
 
 
print("%d"%(table[W]))

Solution (Python):
n,m = map(int,input().split())
C = list(map(int,input().split()))
INF = 50010
dp = [[INF]*(n+1) for _ in range(m+1)]


for i in range(m):
    dp[i+1][0] = 0
    for j in range(1,n+1):
        if j-C[i] >= 0:
            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):
def f(num):
    mn = 20000
    for y in c:
        if y > num/2:
            break
        mn = min(mn, yen[y]+yen[num-y])
    return mn

n, m = map(int, input().split())
c = list(map(int, input().split()))
c = sorted(c)
yen = [0 for i in range(n+1)]
yen[1] = 1
for num in range(2, n+1):
    if num in c:
        yen[num] = 1
    else:
        yen[num] = min(yen[num-1]+1,f(num))

print(yen[n])

Solution (Python):


from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float('inf')


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



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

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

print(dp[n])

Solution (Python):
def solve(n,m,c):
    INF=50001
    dp=[INF]*(n+1)
    dp[0]=0
    for i in range(m):
        v=c[i]
        for j in range(v,n+1):
            if dp[j-v]!=INF:
                dp[j]=min(dp[j-v]+1,dp[j])
    return dp[n]


n,m=map(int,input().split())
c=tuple(map(int,input().split()))
print(solve(n,m,c))

Solution (Python):
def main():
    N, M = map(int, input().split())
    C = list(map(int, input().split()))
    INF = 10**10
    """
    使い回さない方
    dp = [[INF]*(N+1) for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        for y in range(N+1):
            if C[i] > y:
                dp[i+1][y] = dp[i][y]
            else:
                dp[i+1][y] = min(dp[i][y], dp[i+1][y-C[i]]+1)
    print(min([dp[j][N] for j in range(1, M+1)]))
    """
    """ 使い回す方 """
    dp = [INF]*(N+1)
    dp[0] = 0
    for i in range(M):
        for y in range(N+1):
            if C[i] <= y:
                dp[y] = min(dp[y], dp[y-C[i]]+1)
    print(dp[N])


if __name__ == "__main__":
    main()

Solution (Python):
def solve(n, m, c):
    dp = [0] + [float("inf")] * n
    for i in range(1, n + 1):
        added_val = float("inf")
        for coin in c:
            added_val = min(added_val, dp[i - coin]) if 0 <= i - coin else added_val
        dp[i] = min(dp[i], added_val + 1)
    print(dp[n])

if __name__ == "__main__":
    n, m = map(int, input().split())
    c = list(map(int, input().split()))
    solve(n, m, c)

Solution (Python):


import sys

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


dp = [[float('inf')] * (N + 1) for _ in range(M + 1)]
for i in range(len(dp)):
    dp[i][0] = 0


for m in range(M):
    for n in range(N + 1):
        dp[m + 1][n] = min(dp[m + 1][n], dp[m][n])
        next_n = n + c[m]
        if next_n <= N:
            dp[m + 1][next_n] = min(dp[m + 1][n] + 1, dp[m][next_n])





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

Solution (Python):
n, m = [int(x) for x in input().split()]
c = [0] + [int(x) for x in input().split()]
INF = float('inf')
dp = [[0] + [INF for _ in range(n)] for _ in range(2)]

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

print(dp[m % 2][n])

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

c.sort()

dp=[[500000]*(n+1) for i in range(m)]

for ni in range(0,n+1):
    dp[0][ni]=ni

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


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

Solution (Python):
def main():
    n, m = map(int, input().split())
    c = [int(i) for i in input().split()]
    dp = [[10 ** 5 for i in range(n + 1)] for j in range(m + 1)]
    for i in range(m+1):
        dp[i][0] = 0
    for i in range(1, m+1):
        for j in range(1, n+1):
            if c[i - 1] <= j:
                dp[i][j] = min(dp[i][j - c[i - 1]] + 1, dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]
    print(dp[-1][-1])


if __name__ == '__main__':
    main()

Solution (Python):
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:
            dp[i+j] = min(dp[i+j],dp[i]+1)
print(dp[n])

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


dp = [[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]:
            dp[i+1][j] = min(dp[i+1][j-c[i]] + 1, dp[i][j-c[i]] + 1, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
    
print(dp[m][n])

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

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

dp = [N + 1] * (N + 1)
dp[0] = 0

for i in range(N + 1):
    for coin in coins:
        if coin <= i:
            dp[i] = min(dp[i], dp[i - coin] + 1)

print(dp[N])

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

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

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

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

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