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
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N, M = mi()
C = li()

'''
# 二次元DP
dp = dp2(float('inf'), N+1, M+1)
dp[0][0] = 0
for i in range(1, M+1):
    for j in range(N+1):
        #if j == 0:
            #dp[i][j] = 0
        dp[i][j] = min(dp[i-1][j], dp[i][j])
        c = C[i-1]
        if j+c <= N:
            dp[i][j+c] = min(dp[i][j]+1, dp[i-1][j+c])
#print(dp)
print(dp[M][N])
'''

# 1次元DP
dp = [float('inf') for i in range(N+1)]
dp[0] = 0

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

print(dp[N])

Submission status: Accepted

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

"""
m i 枚数
n j 金額

"""

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

Submission status: Accepted

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

INF = 10**9
DP = [INF]*(N+1)
DP[0] = 0

for i in range(1, N+1):
    for c in C:
        if c <= i:
            DP[i] = min(DP[i], DP[i-c]+1)

print DP[N]

Submission status: Accepted

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

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] >= 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, = map(int, input().split())
# n, m = 15, 6
# C = [1, 2, 7, 8, 12, 50]
# DP[i][j]=i種類以内でj円払う最小枚数
inf = 10**10
DP = [[inf for j in range(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] = DP[i][j]
        else:
            DP[i+1][j] = min(DP[i][j], DP[i+1][j-C[i]]+1)
print(DP[m][n])

Submission status: Accepted

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

dp = [[float('inf')]*50010 for _ in range(25)]
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-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:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    n, m = map(int, input().split())
    c = list(map(int, 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):
            if i>=c[j]:
                dp[i] = min(dp[i-c[j]]+1, dp[i])

    print(dp[n])

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
coins = list(map(int, input().split()))
coins.insert(0, 0)
inf = float('inf')
dps = [[inf for _ in range(n + 1)] for _ in range(m + 1)]
# for j in range(n + 1):
#     dps[0][j] = 0
for i in range(m + 1):
    dps[i][0] = 0

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int,input().split())
c = [int(i) for i in input().split()] 

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

Submission status: Accepted

Solution code:
INF = 10**8

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

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

for coin in c:
	for price in range(coin, n + 1):
		d[price] = min(d[price], d[price - coin] + 1)

print(d[n])

Submission status: Accepted

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

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

for i in range(m):
    for j in range(n+1):
        if(j >= c[i]):
            DP[i+1][j] = min(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())
c=list(map(int,input().split()))
c.sort(reverse=True)
#print(c)

dp=[0]
for i in range(1,n+1):
    mini=float("inf")
    for num in c:
        if i-num>=0:
            mini=min(mini,dp[i-num]+1)
    dp.append(mini)

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

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

dp=[[0]*(n+1) for i in range(m)]#dp[i][j]はi番目の硬貨までを使ってj円払う最小の枚数
for i in range(n+1):
    dp[0][i]=i
for j in range(m):
    dp[j][0]=0
    dp[j][1]=1
for i in range(1,m):
    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-1][n])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def make4(initial, L, M, N, O):
    return [[[[initial for i in range(O)]
                for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def make3(initial, L, M, N):
    return [[[initial for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    n, m = MI()
    c = LI()
    dp = [[IINF] * (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+1][j], dp[i][j])
            if j + c[i] <= n:
                dp[i][j+c[i]] = min(dp[i][j+c[i]], dp[i][j] + 1)
                dp[i+1][j+c[i]] = min(dp[i+1][j+c[i]], dp[i][j] + 1)
    print(dp[m][n])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
if __name__ == '__main__':
	n, m = map(int, input().split())
	coin_list = list(map(int, input().split()))
	dp = [50000] * (n + 1)
	dp[0] = 0

	for coin in coin_list:
		for i in range(n - coin + 1):
			if dp[i + coin] > dp[i] + 1:
				dp[i + coin] = dp[i] + 1

	print(dp[-1])

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(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 = list(map(int, input().split()))

cs = list(map(int, input().split()))
_max = 10 ** 1000

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

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

print(dp[n])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: print('Yes' if b else 'No')
YESNO=lambda b: print('YES' if b else 'NO')

def main():
    N,M=map(int,input().split())
    c=list(map(int,input().split()))
    dp=[[INF]*10**6 for _ in range(M+1)]
    dp[0][0]=0
    ans=INF
    for i in range(M):
        for money in range(N+1):
            dp[i+1][money]=min(dp[i+1][money],dp[i][money])
            if money-c[i]>=0:
                dp[i+1][money]=min(dp[i+1][money],dp[i][money-c[i]]+1,dp[i+1][money-c[i]]+1)
    print(dp[M][N])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)
    else:
        print(ans)


def solve():

    N, W = iip()
    dp = [100000] * (100000)
    dp[0] = 0

    coins = iip(True)

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

    #print(dp)
    print(dp[N])







#####################################################ライブラリ集ここから



def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=False):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True, num_only=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    if isinstance(l, list):
        l = l[0] # 間違って要素１個のタプルを渡されても受け取る
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def flatten(l):
    return list(itertools.chain.from_iterable(l))


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    for i in s:
        print(i)


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido = 1): # 関数を二分探索
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r-l > seido:
        #print(x)
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r=x
            else:
                l=x


        elif func(x) > target:
            r = x
        else:
            #print(r, l)
            l = x

    #print(l, r)
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                #for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=[int(j) for j in input().split()]
c=[int(j) for j in input().split()]
dp=[10**18]*(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])

Submission status: Accepted

Solution code:
INF=10**30
n,m=map(int,input().split())
c=list(map(int,input().split()))
dp=[INF]*(n+10)
dp[0]=0
for i in range(1,n+1):
    for j in range(len(c)):
        if(i-c[j]<0):
            continue
        dp[i]=min(dp[i],dp[i-c[j]]+1)
print(dp[n])

Submission status: Accepted

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

dp = [float("inf")]*50001

dp[0] = 0

for  i in range(50001):
    for coin in coins:
        if i+coin > 50000:
            continue
        
        else:
            dp[i+coin] = min(dp[i+coin], dp[i]+1)

print(dp[n])

Submission status: Accepted

Solution code:
# コイン問題
# 個数制限なしナップサックで解く
N, M = map(int, input().split())  # N円, M種類の硬貨
C = list(map(int, input().split()))
dp = [[10**10]*(N+1) for _ in range(M+1)]  # m種類目までの硬貨を使ってn円払うときの最小枚数

dp[0][0] = 0
# M種類の中のi番目のコインを使う
for i in range(M):
    for j in range(N+1):
        # 使わない場合
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        # 使う場合
        if j + C[i] > N:  # 今i番目のコインを使った時にN円を超えるようならダメ
            continue
        # dp[i+1][j]+1は同じ段からの遷移を表している
        dp[i+1][j+C[i]] = min(dp[i][j]+1, dp[i+1][j]+1)
print(dp[M][N])

Submission status: Accepted

Solution code:

def main():
    inf = 1<<29
    n,m = map(int,input().split())
    coins = list(map(int,input().split()))
    dp = [inf]*(n+1)
    dp[0] = 0
    for i in range(1,n+1):
        for j in range(m):
            if i-coins[j]<0:continue
            dp[i] = min(dp[i],dp[i-coins[j]]+1)
    print (dp[n])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_A

INF = float('inf')

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

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

    print(dp[N])

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)] for _ in range(m+1)]
for i in range(1,m+1):
    for w in range(1,n+1):
        if c[i-1]>w:
            dp[i][w]=dp[i-1][w]
        else:
            dp[i][w]=min(dp[i][w-c[i-1]]+1,dp[i-1][w])
print(dp[m][n])

Submission status: Accepted

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

inf=float('inf')

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

DP[0][0]=0

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

print(DP[m][n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
INF = 1145141919810364364334

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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


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

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

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

# print(dp[N])
print(dp[N])

Submission status: Accepted

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

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

stdin = sys.stdin

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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+1):
    if dp[i]==float('inf'):continue
    for j in c:
        if i+j>n:continue
        dp[i+j]=min(dp[i]+1,dp[i+j])
print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

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

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

print(dp[N])

Submission status: Accepted

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

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

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

print(dp[n])

Submission status: Accepted

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

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

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

# print(*dp)
print(dp[n])

Submission status: Accepted

Solution code:
def resolve():
    Nyens, Mtypes = map(int, input().split())  # N円をM種類のコインで最小枚数で払うという問題
    types = list(map(int, input().split()))  # 何円玉があるかのリスト

    def knapsack(Nyens, Mtypes, types):
        # dp[i][j]:i種類目までのコイン限定でj円払うのに必要な最小枚数
        # 最小で無限枚必要として初期化
        dp = [[float('inf')] * (Nyens + 1) for _ in range(Mtypes + 1)]

        # 0円は0枚で払える
        for ii in range(Mtypes):
            dp[ii][0] = 0

        for i in range(Mtypes):
            for j in range(Nyens + 1):
                if j >= types[i]:  # 最小枚数更新の可能性
                    dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - types[i]] + 1)
                else:  # 可能性なし
                    dp[i + 1][j] = dp[i][j]

        return dp[Mtypes][Nyens]

    print(knapsack(Nyens, Mtypes, types))

resolve()

Submission status: Accepted

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

# list of coins
c = list(map(int, input().split()))

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

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


print(dp[n])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
s = input().split()
n = int(s[0])#price
m = int(s[1])#num of kind

coins = input().split()


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

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
coin = list(map(int, input().split()))
    
#dp = [[0]*(w+1) for _ in range(n+1)]
#dp[0] = [0]*(w+1)
dp = [999999]*(n+1)
dp[0] = 0

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

            
print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

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

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

sys.setrecursionlimit(10 ** 8)

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

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

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

Submission status: Accepted

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

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

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

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

print(cash[n])

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

print(dp[m][n])

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
mod = 1000000007

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

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

dp = [0] * (N + 1)

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

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

INF = 10**9

dp = [INF for _ in range(n+1)] #dp[i] := i円での最小枚数
dp[0] = 0
for i in range(m):
    if C[i] < n+1:
        dp[C[i]] = 1

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

print(dp[n])