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
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

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

    print(dp[m][n])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

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

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


# ===CODE===


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

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

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

    print(dp[n])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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


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

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


if __name__ == '__main__':
    resolve()

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

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

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

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

dp[0] = 0

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

Submission status: Accepted

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

Submission status: Accepted

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

#print(c)

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

Submission status: Accepted

Solution code:
INF = 10 ** 20

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

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

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

dp[0] = 0

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

Submission status: Accepted

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

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

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

print(dp[m][n])

Submission status: Accepted

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

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

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

print(dp[m][n])

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(dp[n])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
c = list(map(int, input().split()))
# dp[i][j] = i 番目までを使用して総和がj になる組み合わせ
INF = 5 * 10 ** 4
dp = [[INF] * (n + 1) for _ in range(m + 1)]
dp[0][0] = 0
for i in range(1, m + 1):
    for j in range(n + 1):
        if j >= c[i - 1]:
            dp[i][j] = min(
                dp[i - 1][j], dp[i - 1][j - c[i - 1]] + 1, dp[i][j - c[i - 1]] + 1
            )# dp[i - 1][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()))
# dp[i][j] = i 番目までを使用して総和がj になる組み合わせ
INF = 5 * 10 ** 4
dp = [[INF] * (n + 1) for _ in range(m + 1)]
dp[0][0] = 0
for i in range(1, m + 1):
    for j in range(n + 1):
        if j >= c[i - 1]:
            dp[i][j] = min(
                dp[i - 1][j], dp[i - 1][j - c[i - 1]] + 1, dp[i][j - c[i - 1]] + 1
            )
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[m][n])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

print(dp[M][N])

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

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

Submission status: Accepted

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

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
import sys

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
INF = 10 ** 10


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

inf = float("inf")
dp = [inf for _ in range(n+1)] #最小化問題の時はinfのほうが良いのかな
dp[0] = 0

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


print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

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


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

print(dp[m][n])

Submission status: Accepted

Solution code:
def f(num):
    mn = 20000
    for y in c:
        if y > num/2:
            break
        mn = min(mn, yen[y]+yen[num-y])
    return mn

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

print(yen[n])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from pprint import pprint
import sys

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


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

# dp[i] := ちょうどi円支払うときのコインの最小枚数

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

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

print(dp[n])

Submission status: Accepted

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


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

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# DPL_1_A - コイン問題　

import sys

N, M = map(int, sys.stdin.readline().strip().split())  # N払う　コイン種類M 枚
c = list(map(int, sys.stdin.readline().strip().split()))

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


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


# for i in range(len(dp)):
#     print(dp[i])

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

c.sort()

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

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

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

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

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# i番目までのコインを使ってj円を支払うときの最小枚数
dp = [[INF] * (n+1) for _ in range(m+1)]
dp[0][0] = 0

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(dp[N])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

# dp[i+1][x]:i種類のコインを使ってxを支払う際の最小のコイン枚数
dp = [[float('inf')]*(n+1) for _ in range(m+1)]
dp[0][0] = 0
for i in range(m):
    for x in range(n+1):
        dp[i+1][x] = dp[i][x]

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

Submission status: Accepted

Solution code:
INF = 10 ** 18
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(c[i], n + 1):
        dp[j] = min(dp[j], dp[j - c[i]] + 1)

print(dp[n])

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
C=list(map(int,input().split()))
dp=[0]+[50001 for _ in range(N)]


for i in range(M):
  for j in range(C[i],N+1):
    if C[i] > N:
      break
    elif dp[j-C[i]] != 50001:
      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)
dp[0]=1

for i in range(m):
    for j in range(n+1):
        if dp[j]!=0:
            if j+C[i]<=n:
                if dp[j+C[i]]==0:
                    dp[j+C[i]]=dp[j]+1
                else:
                    dp[j+C[i]]=min(dp[j]+1,dp[j+C[i]])
    #print(dp)
print(dp[n]-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+1)]

for i in range(n+1):
    for c in C:
        if i + c  <= n:
            dp[i+c] = min(dp[i+c],dp[i]+1) if dp[i] != float('inf') else 1
print(dp[n])

Submission status: Accepted

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

inf = 10 ** 6

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

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

Submission status: Accepted

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

N = [float('inf')] * (50000 + 1)
N[0] = 0
for i in range(1, 50000 + 1):
    for c in C:
        if i - c < 0:
            continue
        N[i] = min(N[i - c] + 1, N[i])

print(N[n])

Submission status: Accepted

Solution code:
INF = 10 ** 7
def main():
    N,M = map(int,input().split())
    coin = list(map(int,input().split()))
    dp = [INF] * (N + 1)
    dp[0] = 0
    for c in coin:
        for i in range(c,N + 1):
            dp[i] = min(dp[i],dp[i - c] + 1)
    print(dp[-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
c=list(map(int,input().split()))
dp=[[10001]*m for i in range(n)] #dp[value][i_coin]
dp.insert(0,[0]*m)
for i in range(m):
  for v in range(1,n+1):
    if i==0:
      dp[v][i]=v//c[i] if v%c[i]==0 else 10001
      continue
    if v<c[i]:
        dp[v][i]=dp[v][i-1]
    else:
      dp[v][i]=min(dp[v][i-1],dp[v-c[i]][i]+1)
print(dp[n][m-1])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
lists=list(map(int,input().split()))
dp=[float("inf") for i in range(N+1)]
dp[0]=0
for i in range(1,N+1):
    for num in lists:
        if i>=num:
            dp[i]=min(dp[i],dp[i-num]+1)
print(dp[N])

Submission status: Accepted

Solution code:
INF = float('inf')
N, M = map(int, input().split())
C = [int(c) for c in input().split()]
T = [[INF] * (N + 1) for _ in range(M + 1)]
for i in range(M + 1):
    T[i][0] = 0

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

ans = []
for i in range(1, M + 1):
    ans.append(T[i][N])

print(min(ans))

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A&lang=ja
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    n,m,*C = map(int, read().split())

    # dp[i] := i円を作るのに必要な最小枚数
    dp = [10**10] * (n+1)
    dp[0] = 0

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

    print(dp[n])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def solve():
    import sys

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

    dp = [float("inf") for _ in range(N+1)]  # dp[i] := i円を作ることができるコインの最小枚数
    dp[0] = 0

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

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

print(dp[n])

Submission status: Accepted

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

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

for i in range(n):
    for money in a:
        next_money = i + money
        if next_money > n:
            continue
        dp[next_money] = min(dp[i] + 1, dp[next_money])

print(dp[n])

Submission status: Accepted

Solution code:
# dp[i][j](各マスの値) = i-1番目の品物の中からj円を支払うときの最小枚数
#  → 個数制限なし   
# <DP初期状態>
#   i\j  0   1   2    3   ...  n (お金(yen))
#   0    0  INF INF  INF  ... INF
#   1    0  INF INF  INF  ... INF
#                 ...
#   m-1  0  INF INF  INF  ... INF
#   m    0  INF INF  INF  ... INF
#  (i番目のコイン)
#
# <DP遷移式>
# if(j >= c_i):  c[i]のコイン採用可
#    dp[i+1] = min(dp[i][j-c[i]]+1     : c[i]を採用する(コイン枚数:1枚増える)
#                , dp[i][j])           : c[i]を採用しない
#                , dp[i+1][j-c[i]]+1)  : c[i]を重複を許して採用
# elif(j < c_j): money[i]のコイン採用不可
#    dp[i+1][j] = dp[i][j]              : c[i]を採用しない
 
n,m = map(int,input().split())
c = list(map(int,input().split()))
 
# DP配列の初期化    
dp = []
for i in range(m+100):
    tmp = [0]
    for j in range(n+99): tmp.append(float('inf'))
    dp.append(tmp)
    
# DP遷移    
for i in range(m):
  #print_dp(dp,i)  
  for j in range(n+1):
    if(j>=c[i]): # i番目のコイン採用可
      dp[i+1][j] = min(dp[i][j-c[i]]+1, 
                       dp[i][j],
                       dp[i+1][j-c[i]]+1)  
    else: # i番目のコイン採用不可
      dp[i+1][j] = dp[i][j]

#print_dp(dp,i+1)    
# 出力
print(dp[m][n])

Submission status: Accepted

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

def solve(N,M):
    dp = [[float('inf')]*(N+1) for _ in range(M+1)]
    C = list(map(int, input().split()))
    dp[0][0] = 0
    for i in range(1,M+1):
        dp[i][0] = 0
        for j in range(1,N+1):
            dp[i][j] = dp[i-1][j]
            if j>=C[i-1]:
                dp[i][j] = min(dp[i][j],dp[i][j-C[i-1]]+1)
    ans = dp[M][N]
    return ans
print(solve(N,M))

Submission status: Accepted

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

def coin():
    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)
    return dp[n]

print(coin())

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

def main():
    n, m = map(int, readline().split())
    c = list(map(int, readline().split()))

    maxnum = 50001
    DP = [maxnum] * (n+1)
    DP[0] = 0
    for ctmp in c:
        for j in range(ctmp, n+1):
            if DP[j-ctmp] == maxnum:
                continue
            else:
                DP[j] = min(DP[j], DP[j-ctmp] + 1)
    
    ans = DP[n]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

INF = 10**7
dp = [INF]*(50010)
dp[0] = 0
dp[1] = 1
# dp[i] : i 円支払う時の最小の枚数
for i in range(50001):
    for coin in li_c:
        if i+coin<50010:
            dp[i+coin] = min(dp[i]+1, dp[i+coin])
print(dp[n])

Submission status: Accepted

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

# dp[i][j] := C[i]までのコインを使ってj円を支払うときのコインの最小枚数
dp = [[10 ** 9] * (N+1) for _ in range(M+1)]
dp[0][0] = 0
for i in range(1,M+1):
    for j in range(N+1):
        if j - C[i-1] >= 0:
            dp[i][j] = min(dp[i][j-C[i-1]]+1, dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[M][N])

Submission status: Accepted

Solution code:
import sys

n, m = map(int, sys.stdin.readline().strip().split())
c = list(map(int, sys.stdin.readline().strip().split()))

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

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

print(dp[n])

Submission status: Accepted

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

INF = 10**5
dp = [INF for i in range(n+1)]
dp[0] = 0

for i in range(n+1):
    for d in D:
        if i+d <= n:
            dp[i+d] = min(dp[i+d],dp[i]+1)
print(dp[n])

Submission status: Accepted

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

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

price = [float("INF")] * (n+1)
price[0] = 0

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

print(price[-1])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

DP = [10 ** 9 for _ in range(N + 1)]
DP[0] = 0

for i in range(N):
    for c in Coins:
        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 = [int(i) for i in input().split()]
dp = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    dp[i][1] = i
for j in range(1, m + 1):
    dp[0][j] = 0
    # dp[1][j] = 1
for i in range(n + 1):
    for j in range(1, m):
        if c[j] > i:
            dp[i][j + 1] = dp[i][j]
        else:
            dp[i][j + 1] = min(dp[i][j], dp[i - c[j]][j + 1] + 1)
print(dp[n][m])

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
d = {0:0}
for i in range(1, n + 1):
    min_ = n + 1
    for j in C:
        if i - j in d:
            tmp = d[i - j] + 1
            if tmp < min_:
                min_ = tmp
    d[i] = min_
print(d[n])

Submission status: Accepted

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

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

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m,*c = map(int,read().split())
INF = 9**9
dp = [INF] * (n+1)

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

print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
c = [int(i) for i in input().split()]
dp = [[float("INF")]*(n+1) for _ in range(m+1)]

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

Submission status: Accepted

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

INF = 1 << 29

# dp table 
NMAX = 500000
dp = [INF] * (NMAX + 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:
n, m = map(int, input().split())
D = list(map(int, input().split()))

INF = int(1e18)

# dp[i]: i円をDで支払うときの最小枚数
dp = [INF] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
    for d in D:
        if i - d >= 0:
            dp[i] = min(dp[i], dp[i - d] + 1)
        else:
            dp[i] = dp[i]

print(dp[n])

Submission status: Accepted

Solution code:
inf = 10**9+7
mod = 10**9+7
n, m = map(int, input().split())
c = list(map(int, input().split()))
dp = [[inf for j in range(n+1)]for i in range(m+1)] #i番目まででj払う時に必要な最小枚数
dp[0][0] = 0
for i in range(m):
    dp[i+1][0] = 0
    for j in range(n):
        if j+1-c[i] >= 0:
            dp[i+1][j+1] = min(dp[i][j+1], dp[i][j+1-c[i]]+1, dp[i+1][j+1-c[i]]+1)
        else:
            dp[i+1][j+1] = dp[i][j+1]
print(dp[m][n])

Submission status: Accepted

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

DP=[inf]*(n+1)
DP[0]=0
for i in range(n+1):
    for c in C:
        if 0<=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())
coins=list(map(int,input().split()))
dp=[float('inf')]*(n+1)
dp[0]=0
for i in range(m):
    for j in range(1,n+1):
        if j>=coins[i]:
            dp[j]=min(dp[j],dp[j-coins[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(1, n+1):
  dpi = 10 ** 9
  for j in range(m):
    if(i-c[j]>=0):
      tmp = dp[i-c[j]] + 1
      if(tmp < dpi):
        dpi = tmp
  dp[i] = dpi
  
  
print(dp[n])