Problem:


Coin Changing Problem

Find the minimum number of coins to make change for n cents using coins of denominations d1, d2,.., dm. The coins can be used any number of times.

Input

n m
d1 d2 ... dm

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



Sample input:
55 4
1 5 10 50


Sample output:
2

Submission status: Accepted

Solution code:
import sys

inf = 1<<30

def solve():
    n, m = map(int, input().split())
    c = [int(i) for i in input().split()]
    c.sort()

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

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

    ans = dp[n]
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
dp = [100000] * (n + 1)
dp[0] = 0
for k in C:
    for j in range(k, n + 1):
        if dp[j] > dp[j - k] + 1:
            dp[j] = dp[j - k] + 1
print(dp[n])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
C = list(map(int, input().split()))
dp = [100000] * (n + 1)
dp[0] = 0
for k in C:
    for j in range(k, n + 1):
        if dp[j] > dp[j - k] + 1:
            dp[j] = dp[j - k] + 1
print(dp[n])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
C = list(map(int, input().split()))
dp = [100000] * (n + 1)
dp[0] = 0
for k in C:
    for i, t in enumerate(zip(dp[k:], dp), start = k):
        a, b = t
        dp[i] = min(a, b + 1)
print(dp[n])

Submission status: Accepted

Solution code:
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] = dp[j - c[i]]+1 if dp[j - c[i]] < dp[j] else dp[j]
print(dp[n])

Submission status: Accepted

Solution code:
def calc_number_of_coin(sum, coins):
    dp = [999999999]*(sum+1)
    dp[0] = 0
    for i in range(len(coins)):
        for j in range(coins[i], sum+1):
            dp[j] = min(dp[j], dp[j-coins[i]]+1)
    return dp[sum]



if __name__ == '__main__':
    # ??????????????\???
    # f = open('input.txt')
    # sum, _ = [int(x) for x in f.readline().strip().split(' ')]
    # coins = [int(x) for x in f.readline().strip().split(' ')]

    sum, _ = [int(x) for x in input().strip().split(' ')]
    coins = [int(x) for x in input().strip().split(' ')]

    # ???????????????
    result = calc_number_of_coin(sum, coins)

    # ???????????¨???
    print(result)

Submission status: Accepted

Solution code:
def calc_number_of_coin(sum, coins):
    dp = [999999999]*(sum+1)    #  ??????????????????????????????????????????????????????????????????dp[sum]????????????????±????????????????????´?????????????9999???????????????????????°
    dp[0] = 0                   #  0??????????????????????????¶???????????°???0???
    
    # i??????????????????????????????????¨????, j????????????????¨???????
    # ?????????????????¨??§???????????????????¨???????1?¨?????????????????????????????????????????????°????¨??????????
    # ????????????i???????????§?????¨??§???????????????????¨????????¢??????????????????????????¶???????
    for i in range(len(coins)):
        for j in range(coins[i], sum+1):
            # dp[j]: ??????????????????????????°????¢?????????????????????°?????????????????´???
            # dp[j - coins[i]] + 1:  ??°???????????¨??§????????????????????£??????????????????????????¨??§?????????????????°???????????±?????????
            #                        ?????????+1???????????§??????????¨???????-coins[i]????????????????????????????????°????????????+1???coins[i]???
            dp[j] = min(dp[j], dp[j-coins[i]]+1)
    return dp[sum]


if __name__ == '__main__':
    # ??????????????\???
    # f = open('input.txt')
    # sum, _ = [int(x) for x in f.readline().strip().split(' ')]
    # coins = [int(x) for x in f.readline().strip().split(' ')]

    sum, _ = [int(x) for x in input().strip().split(' ')]
    coins = [int(x) for x in input().strip().split(' ')]

    # ???????????????
    result = calc_number_of_coin(sum, coins)

    # ???????????¨???
    print(result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M = tuple(map(int, input().split()))
coins = sorted(tuple(map(int, input().split())))

counts = [float("inf") for _ in range(N+1)]
counts[0] = 0

for m in range(M):
    coin = coins[m]
    for n in range(coin, N+1):
        counts[n] = min(counts[n], counts[n-coin] + 1)

print(counts[-1])

Submission status: Accepted

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

INF = 10**12

T = [[INF for i in range(n+1)] for j in range(m)]

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

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

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

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

Submission status: Accepted

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

INF = 10**12

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

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

print(T[n])

Submission status: Accepted

Solution code:
import sys


def getTheNumberOfCoin(n, m, c):
    T = {}
    for j in range(0, n+1):
        T[j] = 100000
    T[0] = 0

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

    return T[n]


n, m = (int(x) for x in sys.stdin.readline().split())
c = sorted([int(x) for x in sys.stdin.readline().split()])

print(getTheNumberOfCoin(n, m, c))

Submission status: Accepted

Solution code:
n = int(input().split()[0])
c = list(map(int,input().split()))
dp = [ i for i in range(n+1) ]

for i in range(2,n+1):
    c2 = filter(lambda n:n<=i,c)
    for j in c2:
        if j <= i and dp[i-j] + 1 < dp[i]:
            dp[i] = dp[i-j] + 1

print(dp[n])

Submission status: Accepted

Solution code:
n = int(input().split()[0])
c = list(map(int,input().split()))
dp = list(range(n+1))

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

print(dp[n])

Submission status: Accepted

Solution code:
def calc_t(i,j):
    global t,c
    if i<0 or j<0:
        return n+2
    #print("get t["+str(i)+","+str(j)+"]")
    if t[i][j]==n+1:
        t[i][j]=min(calc_t(i-1,j),calc_t(i,j-c[i])+1)
    return t[i][j]

ri=raw_input().split(" ")
n=int(ri[0])
m=int(ri[1])
ri=raw_input().split(" ")
c=[0]*m
t=[0]*m
for i in range(m):
    c[i]=int(ri[i])
    t[i]=[0]+[n+1]*n if i!=0 else range(n+1)
c=sorted(c)
#print(c)
#print(t)
for a in range(n+1):
    for b in range(m):
        calc_t(b,a)
print(calc_t(m-1,n))

Submission status: Accepted

Solution code:
n, m = input().split()
n, m = int(n), int(m)
C = [int(c) for c in input().split()]

# Coin Changing Problem
T = [0] + [float('inf')] * n

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

print(T[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

f = dict() #k?????§??????????????????????°??????????????????¨?????°
f[0] = 0
for k in range(1,n+1):
    f[k] = float('inf')
    for c in cs:
        if k - c < 0:
            continue
        f[k] = min(f[k], f[k - c] + 1)

print(f[n])

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    c=list(map(int,input().split()))
    dp=list(range(n+1))
    k=0
    while k<len(c):
        for i in range(n+1-c[k]):
            dp[i+c[k]]=min(dp[i+c[k]],dp[i]+1)
        k+=1
    print(dp[n])

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python2
# coding: utf-8

n, m = map(int, raw_input().split())
c = map(int, raw_input().split())

dp = ['inf'] * 50001
dp[0] = 0;

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

print dp[n]

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
n, m = inpl()
C = sorted(inpl())
DP = list(range(n+1))

for c in C[1:]:
    for i in range(n-c+1):
        if DP[i] + 1 < DP[i+c]:
            DP[i+c] = DP[i] + 1
            
print(DP[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


if __name__ == '__main__':
    n, m = map(int, input().split())
    C = [int(x) for x in input().split()]
    T = [float("inf") for _ in range(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[n])

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
d = list(map(int, input().split()))
inf = float('inf')
dp = [inf for i in range(n+1)]
dp[0] = 0
for i in range(m):
    for j in range(d[i], n+1):
        dp[j] = min(dp[j], dp[j-d[i]]+1)

print(dp[-1])

Submission status: Accepted

Solution code:
def solver(n ,m, coins):
  dp = [[100000] * (n + 1) for i in range(m + 1)]
  for i in range(m + 1): dp[i][0] = 0
  for r in range(1, m + 1):
    for c in range(1, n + 1):
      if 0 > c - coins[r - 1]:
        dp[r][c] = dp[r - 1][c]
      else:
        dp[r][c] = min(dp[r - 1][c], dp[r][c - coins[r - 1]] + 1)
  print(dp[m][n])


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

Submission status: Accepted

Solution code:

if __name__ == '__main__':
	n = input().split()
	c = input().split()
	dp = [50000] * (int(n[0]) + 1)

	for i in range(int(n[1])):
		if int(c[i]) > int(n[0]):
			continue
		dp[int(c[i])] = 1
		for j in range(int(n[0])):
			if int(c[i])+j > int(n[0]):
				break;
			if dp[j] != 50000:
				dp[int(c[i])+j] = min(dp[int(c[i])+j], dp[j]+1)

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

Submission status: Accepted

Solution code:
n,m=map(int,raw_input().split())
c=map(int,raw_input().split())

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

c.remove(1)
c.sort()

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

print dp[n]

Submission status: Accepted

Solution code:
import math
n, m = map(int,input().split(' '))
d = list(map(int,input().split(' ')))
d.sort()
inf = n

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

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

for j in range(m-1,-1,-1):
    for i in range(n+1):
        #for k in range(math.floor(i/d[j])+1):
        if math.floor(i/d[j]) >=1:
            k=1
        else:
            k=0
        r = k*d[j]
        #print(i,j,k)
        dp[i][j] = min( dp[i][j], dp[i][j+1], dp[i-r][j]+k ) 
        #print("dp:",i,j,dp[i][j])
print(dp[n][0])

Submission status: Accepted

Solution code:
def cs(n, p, c):
    global count, m
    if n % c[0] == 0:
        count = min(count, p + n // c[0])
        return count
    elif p + n // c[0] >= count:
        return n
    elif c[0] < n:
        return min(cs(n - c[0], p + 1, c), cs(n, p, c[1:]))
    else:
        return cs(n, p, c[1:])

n, m = map(int, input().split())
c = list(map(int, input().split()))
c.sort(reverse = True)
count = n
print(cs(n, 0, c))

Submission status: Accepted

Solution code:
def main():
    n, m = list(map(int, input().split()))
    coins = list(map(int, input().split()))

    dp = [float('inf')] * 50001
    dp[0] = 0

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

    print(dp[n])
main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May 26 12:16:54 2018
DPL-1A Rec Call Revised
@author: maezawa
"""

n, m = list(map(int, input().split()))
c = list(map(int, input().split()))
c.sort()
dp = [float('inf') for _ in range(n+1)]
dp[0] = 0
#print(n,m)
#print(c)
#print(*dp, sep='\n')

for j in range(1,n+1):
    temp = []
    for i in range(m):
        if j < c[i]:
            continue
        else:
            temp.append(dp[j-c[i]]+1)
    dp[j] = min(temp)

print(dp[n])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
c = sorted([int(i) for i in input().split()])
dp = [[0 for j in range(n+1)] for i in range(m+1)]
dp[1] = [int(i) for i in range(n+1)]
for i in range(2, m+1):
    for j in range(n+1):
        if j - c[i-1] > -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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
#!/usr/bin/env 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])

Submission status: Accepted

Solution code:
#!/usr/bin/env 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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
#!/usr/bin/env 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])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(100000000)

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

# num 番目までのコインを使い、yen 円支払うときに必要な枚数
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))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
# 37

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

# dp[i] = i円の支払う時のコインの最小枚数
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])

Submission status: Accepted

Solution code:
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)]

#0行目の初期化
for i in range(1, n+1):
    T[0][i] = infty
#0列目の初期化
for i in range(m+1):
    T[i][0] = 0
#1行目の初期化
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

#dp[i][j]をi番目まででj支払える最小枚数
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])

Submission status: Accepted

Solution code:

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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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[i] := i円払うのに必要な枚数
    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()

Submission status: Accepted

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

    dp[weight <= W+1] = 重さを固定した時の最小価値
    dp[W+1] = 重さがWより大きい時の最小価値
    """
    W2 = W + 1              # dp[W+1] に W より大きい時の全ての場合の情報を持たせる
    dp_max = float("inf")   # 総和価値の最大値
    dp = [dp_max] * (W2 + 1)
    dp[0] = 0               # 重さ 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())                                # N: 品物の種類 W: 重量制限

# cost_list = []
# weight_list = []
# for _ in range(N):
#     """ cost と weight が逆転して入力されている場合有り """
#     weight, cost = map(int, input().split())
#     cost_list.append(cost)
#     weight_list.append(weight)

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

print(coin(single=False))


############################################################################################

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

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

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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)
# pprint(dp)
print(dp[m][n])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

DP=[i for i in range(N+1)]
#print(DP)
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])
print(DP[-1])