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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:



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


#i番目までのコインを使えるときに、j円を作る場合の、コインの最小枚数を求める
for i in range(M):
    for j in range(N+1):
        # i番目を使えない場合
        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])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# import numpy as np

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
        #print('\n')
        #print(f'kingaku:{kingaku}, kinds:{kinds}')
        #print(G[kinds-1][kingaku])
        #print(G[kinds][kingaku-C[kinds-1]]+1)
        G[kinds][kingaku] = min(G[kinds-1][kingaku], G[kinds][kingaku-C[kinds-1]]+1)
        #print(f'index{kinds},{kingaku}')
        #print(G[kinds][kingaku])

#print(G)
print(G[M][N])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!python3

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_A
# めちゃくちゃナップサックっぽい。ってかナップサックじゃん
# 本ではdpテーブルに当たるTを1次元配列にすることによってメモリを削減しているが、ここではしない。

# dpテーブルは初期化と、更新が必要でそれらを意識しながら実装する。
# C ... (m,) i番目のコインの額面
# dp ... (m, n+1) i番目まで(それを含む)のコインをつかってj円払うときのコインの最小枚数

INF = 1e5

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

# dpテーブルの作成 minを取りながら更新するときは初期値にINFをぶちこんでおくとよい
dp = [[INF] * (n + 1) for _ in range(m)]  # (m,n+1)のリストの作成

# dpテーブルの初期化
# dp[:][0] は常に0 ∵ 0円はコインを一つも使わなければ良い
# dp[0][:] は即座に決定する。 ∵ dp[0][j]%C[0] == 0ならばdp[0][j]//C[0]の枚数で j 円を達成可能だから
for i in range(m):
    dp[i][0] = 0
for j in range(1 + n):
    dp[0][j] = j  # いまC[0]は必ず1と問題文にあるので、これを用いることにする。

# dpテーブルの更新
# 更新則は T[i][j]=min(T[i-1][j], T[i][j-C[i]]+1)
# 1項目 i-1までのコインでj円が作れるとき、i番目のコインを使わなくてもj円を作る枚数は変わらない。
# 2項目 i番目のコインを使ってちょうどj円を達成するには、j-C[i]円のときに達成可能なコインの枚数に1を足せば良い
# 最小のコインの枚数を知りたいのだから上記の小さい方を採用すれば良い
from itertools import product
# Z字にdpを更新していく.初期値のある列と行は省略
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:
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[price]=num of coins?

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
INF = 10**10
N,M = map(int,input().split())
Coins = list(map(int,input().split()))
Coins.sort()
# DP[x種類目までのコイン][n円を支払う]
# index1 0,1(1種類め),...(n種類め)
# index2 0円,1円,2円... 
# DP[m+1][n+1]で作成
DP = [ [INF]*(N+1) for _ in range(M+1) ]

# 0円の場合の支払いに必要な枚数は 0
for i in range(1,M+1):
    DP[i][0] = 0

# 1円のみで支払う場合
for i in range(1,N+1):
    DP[1][i] = i
# 2種類め以降を使う場合
for m in range(2,M+1):
    for n in range(1,N+1):
        # 支払うのは n円
        # 1枚 c円
        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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
c=list(map(int,input().split()))
c.sort()
# print(c) #DB
dp=[[0 for j in range(n+1)] for i in range(m)] # i番目(0<=i<=m-1)までのコインを使用してj円(0<=j<=n)を支払う際の最少の枚数
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(c[i],dp[i]) #DB
print(dp[m-1][n])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

# 0はdummy
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])

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque

def min_coin_select(C, m, n):
    DP = [float('inf')] * (n+1)
    DP[0] = 0
    # Cのindexが合わないので左をゼロ埋め。Cはdequeとする。
    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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# DPL 1 A

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

Submission status: Accepted

Solution code:
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)]#50000が上限
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env 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():
    # https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_A
    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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

n, m = LI()
c = LI()
c = sorted(c)

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

for i in range(n+1):
    for coin in c:
        if (i+coin <= n) and (dp[i+coin] > dp[i]+1):
            dp[i+coin] = dp[i]+1

print(dp[n])

Submission status: Accepted

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

import sys

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

N,M=MAP()
C=LIST()

dp=[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])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, m = MAP()
c = LIST()

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

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

Submission status: Accepted

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

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

for i in range(m + 1):
    for j in range(n + 1):
        if i == 0 and j == 0:
            dp[i][j] = 0
        elif i == 0:
            dp[i][j] = 1000000000
        elif j == 0:
            dp[i][j] = 0
        else:
            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]

ans = 10 ** 10
for i in range(m + 1):
    ans = min(ans, dp[i][n])
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)
dp = []
coins = []
INF = 9999999

def change(n, m):
    if n == 0:
        return 0
    if dp[n] == INF:
        res = INF
        for j in range(0, m):
            if n - coins[j] >= 0:
                res = min(res, change(n - coins[j], m) + 1)
        dp[n] = res
    return dp[n]

line = input()
n, m = list(map(int, line.split()))
line = input()
d = list(map(int, line.split()))
coins = sorted(d)
coins.reverse()
dp = [INF] * (n + 1)
change(n, m)
print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
L = list(map(int,input().split()))
dp = [float('inf')]*50001
for i in range(len(L)):
    dp[L[i]] = 1
for i in range(2,50001):
    for j in range(len(L)):
        if i-L[j] >= 1:
            dp[i] = min(dp[i-L[j]]+1,dp[i])
print(dp[n])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
*c, = map(int, input().split())
c.sort()
dp = [2**32 for _ in range(n+1)]
for i in range(n+1):
    dp[i] = i
for i in range(1, m):
    for j in range(n+1):
        if (j-c[i]) >= 0:
            dp[j] = min([
                dp[j],
                dp[j-c[i]]+1
            ])
        else:
            dp[j] = dp[j]
print(dp[n])

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
ink = list(map(int, input().split()))
ink.sort()
array = [0 for i in range(n+1)]

array[1] = 1
for i in range(2, n+1):
	if i in ink:
		array[i] = 1
	else:
		mini = i
		for j in ink[::-1]:
			if j < i:
				if mini > 1 + array[i-j]:
					mini = 1 + array[i-j]
		array[i] = mini
print(array[n])

Submission status: Accepted

Solution code:
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(1, N+1):
    for c in C:
        if i-c  >= 0:
            dp[i] = min(dp[i], dp[i-c]+1)

print(dp[N])

Submission status: Accepted

Solution code:
n,m,*c=map(int,open(0).read().split())
c=sorted(c)
dp=[float("inf")]*50001
dp[0]=0
for i in range(50001):
    for j in c:
        if i+j>50000:
            continue
        else:
            dp[i+j]=min(dp[i+j],dp[i]+1)
print(dp[n])

Submission status: Accepted

Solution code:
def min_coin(i):
    if coin_dp[i]!=50001:
        return(coin_dp[i])
n,m=map(int,input().split())
coin_dp=[float("inf")]*(n+1)
coin_dp[0]=0
coin=list(map(int,input().split()))
for i in range(n):
    for j in coin:
        if i+j>n:
            continue
        else:
            coin_dp[i+j]=min(coin_dp[i+j],coin_dp[i]+1)
print(coin_dp[-1])

Submission status: Accepted

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

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

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

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


print(dp[n])

Submission status: Accepted

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

n, m = map(int, input().split())
c = [ int(x) for x in input().split() ]

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

for i in range(1, 50001):
    cand = float('inf')
    for j in c:
        if i-j < 0:
            continue 
        else:
            cand = min(cand, dp[i-j] + 1)
    dp[i] = cand

print (dp[n])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
c=list(map(int,input().split()))
c.sort()
c.reverse()
def roop(n,m,c,check,nowans,nown,ans):
    if nowans+nown//c[check]>=ans:return ans
    if c[check]==1:
        return min(nowans+nown,ans)
    if c[check]>nown:
        ans=roop(n,m,c,check+1,nowans,nown,ans)
    elif c[check]<=nown:
        for i in range(nown//c[check],-1,-1):
            ans=roop(n,m,c,check+1,nowans+i,nown-i*c[check],ans)
    return ans
print(roop(n,m,c,0,0,n,n))

Submission status: Accepted

Solution code:
inf = 1 << 60
n,m = map(int, input().split())
c = list(map(int, input().split()))
dp = [inf] * (n + 1)
dp[0] = 0
for ci in c:
    for i in range(0, n + 1 - ci):
        dp[i + ci] = min(dp[i + ci], dp[i] + 1)
print(dp[n])