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: Time Limit Exceeded

Solution code:
import math
#import sys
#sys.setrecursionlimit(50001)

nm = input().split(' ')
n = int(nm[0])
m = int(nm[1])
c = list(map(int, input().split(' ')))

dp = {}

# cの要素のうちp番目以降を組み合わせてtを作れるか?作れるならその数を返す
def solve(p, t, num):
  if ((p, t, num) in dp):
    return dp[(p, t, num)]

  # 使う/使わないの枝をたどって0になったらOK
  if (t == 0):
#     print("(p, t, num) = (" + str(p) + ", " + str(t) + ", " + str(num) + ")")
    return (True, num)
  # p, tが不正な値になればその枝は終了
  if (p == m or t < 0):
    return (False, num)

  ans = []

  # p番目を1枚だけ使う
  # p番目を使ったらtから引いてもう一度pまたは次へ, 使わなければtのまま次へ
#   ans.append(solve(p, t-c[p], num+1))
#   ans.append(solve(p+1, t-c[p], num+1))
#   ans.append(solve(p+1, t, num))
  # p番目を0から使える枚数ギリギリまで使い次へ（再帰が深くなり過ぎるケースの対策）
  cnt = math.floor(t / c[p])
  for i in range(0, cnt+1):
    ans.append(solve(p+1, t-c[p]*i, num+i))

  # 最小のnumがansになる
  ansNum = 50000
#   ansNum = min(list(map(lambda e: e[1], filter(lambda e: e[0], ans))))
  for e in ans:
    if (e[0] and e[1] < ansNum):
      ansNum = e[1]

  ret = (list(map(lambda e: e[0], ans)).count(True) > 0, ansNum)
  dp[(p, t, num)] = ret
  return ret

print(solve(0, n, 0)[1])

Submission status: Time Limit Exceeded

Solution code:
import math

nm = input().split(' ')
n = int(nm[0])
m = int(nm[1])
c = list(map(int, input().split(' ')))

dp = {}
minNum = 50000

# cの要素のうちp番目以降を組み合わせてtを作れるか?作れるならその数を返す
def solve(p, t, num):
  global minNum

  if ((p, t, num) in dp):
    return dp[(p, t, num)]

  # 使う/使わないの枝をたどって0になったらOK
  if (t == 0):
#     print("(p, t, num) = (" + str(p) + ", " + str(t) + ", " + str(num) + ")")
    if (num < minNum):
      minNum = num
    return (True, num)
  # p, tが不正な値または暫定最小より大きなnumになればその枝は終了
  if (p == m or t < 0 or num > minNum):
    return (False, num)

  ans = []

  # p番目を1枚だけ使う
  # p番目を使ったらtから引いてもう一度pまたは次へ, 使わなければtのまま次へ
#   ans.append(solve(p, t-c[p], num+1))
#   ans.append(solve(p+1, t-c[p], num+1))
#   ans.append(solve(p+1, t, num))
  # p番目を0から使える枚数ギリギリまで使い次へ（再帰が深くなり過ぎるケースの対策）
  cnt = math.floor(t / c[p])
  for i in range(0, cnt+1):
    ans.append(solve(p+1, t-c[p]*i, num+i))

  # 最小のnumがansになる
  ansNum = 50000
#   ansNum = min(list(map(lambda e: e[1], filter(lambda e: e[0], ans))))
  for e in ans:
    if (e[0] and e[1] < ansNum):
      ansNum = e[1]

  ret = (list(map(lambda e: e[0], ans)).count(True) > 0, ansNum)
  dp[(p, t, num)] = ret
  return ret

print(solve(0, n, 0)[1])

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
sys.setrecursionlimit(50001)

nm = input().split(' ')
n = int(nm[0])
m = int(nm[1])
c = list(map(int, input().split(' ')))
c.sort()
c.reverse()

dp = {}

# cの要素のうちp番目以降を組み合わせてtを作れるか?作れるならその数を返す
def solve(p, t, num):
  if ((p, t, num) in dp):
    return dp[(p, t, num)]

  # 使う/使わないの枝をたどって0になったらOK
  if (t == 0):
#     print("(p, t, num) = (" + str(p) + ", " + str(t) + ", " + str(num) + ")")
    return (True, num)
  # p, tが不正な値になればその枝は終了
  if (p == m or t < 0):
    return (False, num)

  ans = []

  # p番目を1枚だけ使う
  # p番目を使ったらtから引いてもう一度pまたは次へ, 使わなければtのまま次へ
  ans.append(solve(p, t-c[p], num+1))
  ans.append(solve(p+1, t-c[p], num+1))
  ans.append(solve(p+1, t, num))
  # p番目を0から使える枚数ギリギリまで使い次へ（再帰が深くなり過ぎるケースの対策）
#   cnt = math.floor(t / c[p])
#   for i in range(0, cnt+1):
#     ans.append(solve(p+1, t-c[p]*i, num+i))

  # 最小のnumがansになる
  ansNum = 50000
#   ansNum = min(list(map(lambda e: e[1], filter(lambda e: e[0], ans))))
  for e in ans:
    if (e[0] and e[1] < ansNum):
      ansNum = e[1]

  ret = (list(map(lambda e: e[0], ans)).count(True) > 0, ansNum)
  dp[(p, t, num)] = ret
  return ret

print(solve(0, n, 0)[1])

Submission status: Time Limit Exceeded

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

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

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

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

print(dp[n][0])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

def min_number(i,nn):
    if i == m:
        return dp[i][nn]
    if dp[i][nn] != float('inf'):
        return dp[i][nn]
    if nn < c[i]:
        dp[i][nn] = min_number(i+1,nn)
    else:
        temp = []
        j = 0
        while nn >= j*c[i]:
            temp.append(min_number(i+1, nn-j*c[i])+j)
            j += 1
        dp[i][nn] = min(temp)
    return dp[i][nn]

print(min_number(0,n))

Submission status: Time Limit Exceeded

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

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

# num 番目までのコインを使い、yen 円支払うときに必要な枚数
def func(num, yen):
	if num < 0 or yen < 0:
		return 10 ** 18
	if num == 0 and yen == 0:
		return 0
	'''
	if not (num, yen) in DP:
		DP[(num, yen)] = min(func(num - 1, yen), func(num, yen - c[num]) + 1)
	return DP[(num, yen)]
	'''
	return min(func(num - 1, yen), func(num, yen - c[num]) + 1)

print(func(m - 1, n))

Submission status: Time Limit Exceeded

Solution code:
import itertools as it
n, m = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
for i in range(m):
    # print(f"{i}枚の組:{list(it.product(c, repeat=i))}")
    for comb in it.product(c, repeat=i):
        if sum(comb) == n:
            # print(f"sum({comb})={n}")
            print(i)
            exit()

Submission status: Memory Limit Exceeded

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

cc = []
for i in c:
  x = n // i
  for j in range(x):
    cc.append(i)
coins = len(cc)
# print(cc)
dp = [ [0 for i in range(n + 1)] for j in range(coins)]

for i in range(n + 1):
  dp[0][i] = i // cc[0]
for i in range(1, coins):
  for j in range(n + 1):
    if(j - cc[i] >= 0):
      dp[i][j] = min(dp[i - 1][j - cc[i]] + 1, dp[i - 1][j])
    else:
      dp[i][j] = dp[i - 1][j]
      
#for i in range(coins):
 # for j in range(n + 1):
 #   print(dp[i][j], end = "")
  #print()
      
print(dp[coins - 1][n])

Submission status: Memory Limit Exceeded

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

cc = []
for i in c:
  x = n // i
  for j in range(x):
    cc.append(i)
coins = len(cc)
# print(cc)
dp = [ [0 for i in range(n + 1)] for j in range(coins)]

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

Submission status: Memory Limit Exceeded

Solution code:
from itertools import combinations_with_replacement as C
n, m = map(int, input().split())
coin = sorted(list(map(int, input().split())))
if n in coin:
    print(1)
else:
    end = n // coin[0] + 1
    b = False
    for i in range(2, end):
        for tup in list(C(coin, i)):
            if sum(tup) == n:
                print(i)
                b = True
                break
        if b: break

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
mo = list(map(int,input().split()))
dp = [float("inf") for i in range(n+2)]
dp[0] = 0
for i in range(n+1):
    for j in mo:
        if i+j <= n:
            dp[i+j] = min(dp[i+j],dp[i]+1)
print(dp[n])

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
c = list(map(int,input().split()))
dp = [float("inf") for i in range(a+2)]
dp[0]=0
for i in range(a+1):
    for j in c:
        if i + j <= a:
            dp[i+j] = min(dp[i+j],dp[i] + 1)
            
print(dp[a])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import copy

N, M = map(int, input().split())
c = [0]
c += list(map(int, input().split()))
memo = [N] * (N+1)
flag = [False] * (N+1)
flag[0] = True
memo[0] = 0

for i in range(1, N+1):
    if not flag[i]:
        flag[i] = True
        for j in range(1, M+1):
            if i >= c[j]:
                memo[i] = min(memo[i], memo[i-c[j]] + 1)

print(memo[N])

Submission status: Accepted

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

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

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

mon.sort(reverse = True)

count = n

print(coin(n, 0, mon))

Submission status: Accepted

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

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

for i in range (n+1):
    for j in range (len(c)):
        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()))

INF = 10**100
dp = [INF]*500000
dp[0] = 0

for i in range (n+1):
    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 = list(map(int, input().split()))
c.sort() # sortしなくてもこのアルゴリズムは有効

dp = [50001 for i in range(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[n])

Submission status: Accepted

Solution code:
nm = raw_input().split()
n = int(nm[0])
m = int(nm[1])
d = raw_input().split()

c = [0] * 100000
c[0] = 0

for i in range(n):
    min = 100000
    for j in range(m):
        if int(d[j]) < i + 2:
            x = c[i + 1 - int(d[j])]
            if x < min:
                min = x
    c[i + 1] = min + 1

print c[n]

Submission status: Accepted

Solution code:
inf = 2**31
n,m = map(int,raw_input().split())
coins = map(int,raw_input().split())
dp = [inf]*(n+1)
dp[n] = 0
while dp[0] == inf:
    for coin in coins:
        for i in range(n,coin-1,-1):
            if dp[i] < inf:
                dp[i-coin] = min(dp[i-coin],dp[i]+1)
print dp[0]

Submission status: Accepted

Solution code:
import sys

def min_coins(N, M, ws):
    dp = [-(1 << 32)] * (N + 1)
    dp[0] = 0
    
    for i in range(M):
        for j in range(ws[i], N + 1):
            dp[j] = max(dp[j - ws[i]] - 1, dp[j])
    
    
    return abs(dp[-1])
    
    
if __name__ == '__main__':
    N = sys.stdin.readline()
    N, M = N.split()
    N, M = int(N), int(M)
    arr = sys.stdin.readline()
    arr = arr.split()
    arr = map(lambda x: int(x), arr)
    
    sys.stdout.write(str(min_coins(N, M, arr)))
    sys.stdout.write('\n')

Submission status: Accepted

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

payment, _ = map(int, readline().split())
coin = list(map(int, readline().split()))

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

for ci in coin:
    for pi in range(ci, len(dp)):
        if dp[pi] > dp[pi - ci] + 1:
            dp[pi] = dp[pi - ci] + 1
print(dp[-1])

Submission status: Accepted

Solution code:
def getTheNumberOfCoin(n,m,C):
    T=[float('inf')]*(n+1)
    T[0]=0

    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)
    return T[n]

n,m = map(int,raw_input().split())
C = map(int,raw_input().split())
print getTheNumberOfCoin(n,m,C)

Submission status: Accepted

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

Submission status: Accepted

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

c.sort(reverse = True)

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

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

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

print(dp[m][n])

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
l = map(int, raw_input().split())
INF = 1<<31
dp = [INF]*(n+1)
dp[0] = 0
for c in l:
    for i in range(n-c+1):
        if dp[i] != INF:
            dp[i + c] = min(dp[i] + 1, dp[i + c])
print dp[n]

Submission status: Accepted

Solution code:
from __future__ import division
from sys import stdin, maxint

def solve(n, m, ds):
    dp = [maxint] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        for j in range(m):
            if i >= ds[j]:
                dp[i] = min(dp[i], dp[i - ds[j]] + 1)

    return dp[n]

if __name__ == '__main__':
    n, m = map(int, stdin.readline().strip().split())
    ds = map(int, stdin.readline().strip().split())
    print(solve(n, m, ds))

Submission status: Accepted

Solution code:
"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A
"""

from __future__ import division
from sys import stdin, maxint

def solve(n, m, ds):
    dp = [maxint] * (n + 1)
    dp[0] = 0
    for i in range(m):
        for j in range(ds[i], n + 1):
            dp[j] = min(dp[j], dp[j - ds[i]] + 1)

    return dp[n]

if __name__ == '__main__':
    n, m = map(int, stdin.readline().strip().split())
    ds = map(int, stdin.readline().strip().split())
    print(solve(n, m, ds))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
a = raw_input().split()
n = int(a[0])
m = int(a[1])

C = map(int,raw_input().split())
T = [float('inf') for _ in xrange(n+1)]

def getTheNumberOfCoin():
    T[0] = 0
    for i in xrange(m):
        for j in xrange(C[i],n+1):
            T[j] = min(T[j], T[j-C[i]]+1)

    print T[n]
    return 0

getTheNumberOfCoin()

Submission status: Accepted

Solution code:
import heapq

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


def fsp(n, coins):
    paid = [False] * (n + 1)
    paid[0] = True
    queue = list((1, v) for v in coins)
    heapq.heapify(queue)
    while queue:
        num, value = heapq.heappop(queue)
        if paid[value]:
            continue
        paid[value] = True
        for c in coins:
            new_value = value + c
            # Because of link cost is constant 1, it is reliably shortest-path.
            if new_value == n:
                return num + 1
            elif new_value > n or paid[new_value]:
                continue
            heapq.heappush(queue, (num + 1, value + c))


print(fsp(n, coins))

Submission status: Accepted

Solution code:
class DP:
    def __init__(self, value, variety, coins):
        self.value = value
        self.variety = variety
        self.coins = coins
        self.DP = [[0 for _ in range(value + 1)] for _ in range(variety)]
        self.DPinit()

    def monitor(self):
        for (i, row) in enumerate(self.DP):
            print(coins[i], row)

    def DPinit(self):
        for row in self.DP:
            row[1] = 1
        self.DP[0] = [i for i in range(self.value + 1)]

    def DPcomp(self):
        for m in range(self.variety):
            if m == 0:
                continue
            for n in range(self.value + 1):
                self.DP[m][n] = self.numberOfCoin(m, n)

    def numberOfCoin(self, m, n):
        if n >= self.coins[m]:
            return min(self.DP[m - 1][n], self.DP[m][n - self.coins[m]] + 1)
        else:
            return self.DP[m - 1][n]

    def answer(self):
        self.DPcomp()
        return self.DP[self.variety - 1][self.value]

if __name__ == "__main__":
    status = list(map(int,input().split()))
    coins = list(map(int,input().split()))
    dp = DP(status[0],status[1],coins)
    print(dp.answer())

Submission status: Accepted

Solution code:
from itertools import product

class DP:
    def __init__(self, value, variety, coins):
        self.value = value
        self.variety = variety
        self.coins = coins
        self.DP = [[0 for _ in range(value + 1)] for _ in range(variety)]
        self.DPinit()

    def DPinit(self):
        for row in self.DP:
            row[1] = 1
        self.DP[0] = [i for i in range(self.value + 1)]

    def DPcomp(self):
        for (m, n) in product(list(range(1, self.variety)),list(range(self.value + 1))):
                self.DP[m][n] = self.numberOfCoin(m, n)

    def numberOfCoin(self, m, n):
        if n >= self.coins[m]:
            return min(self.DP[m - 1][n], self.DP[m][n - self.coins[m]] + 1)
        else:
            return self.DP[m - 1][n]

    def answer(self):
        self.DPcomp()
        return self.DP[self.variety - 1][self.value]


if __name__ == "__main__":
    status = list(map(int,input().split()))
    coins = list(map(int,input().split()))
    dp = DP(status[0],status[1],coins)
    print(dp.answer())

Submission status: Accepted

Solution code:
from itertools import product

value, variety = map(int, input().split())
coins = list(map(int, input().split()))
dp = [float("inf") for _ in range(value + 1)]
dp[0] = 0
for (c,j) in product(coins,list(range(value + 1))):
    if c <= j:
        dp[j] = min(dp[j], dp[j - c] + 1)
    else:
        dp[j] = dp[j]
print(dp[value])

Submission status: Accepted

Solution code:
n,m=map(int,raw_input().split())
c=map(int,raw_input().split())
dp=[[0]+[float('inf')]*n]+[[0]+[float('inf')]*n for i in xrange(m)]
for i in xrange(m):
    for j in xrange(n+1):
        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[m][n])

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
c = map(int, raw_input().split())
dp = [n+1] * (n+1)
dp[n] = 0
for rest in xrange(n, 0, -1):
    for i in xrange(m):
        if c[i] <= rest:
            dp[rest - c[i]] = min(dp[rest - c[i]], 1 + dp[rest])
print dp[0]

Submission status: Accepted

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

dp = [0] + [50000]*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:

import sys

inf_val = 10**10

m, n = map(int, sys.stdin.readline().split())
numbers = map(int, sys.stdin.readline().split())

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

for x in numbers:
    for y in xrange(x, m+1):
        dp[y] =  min(dp[y-x]+1, dp[y])

print dp[m]

Submission status: Accepted

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

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

for coin in m:
    if coin <= n:
        c[coin] = 1
        coins.append(coin)

for p in range(2,n+1):
    minc = c[p]
    if minc <= 2:
        continue
    for coin in coins:
        if p > coin:
            if minc > c[p-coin]+1:
                minc = c[p-coin]+1
    c[p] = minc

print(c[n])

Submission status: Accepted

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

for i in range(0, n + 1):
    if dp[i] < 10000:
        for j in d:
            if i + j <= n:
                dp[i + j] = min(dp[i] + 1, dp[i + j])

print(dp[n])

Submission status: Accepted

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

"""
input:
15 6
1 2 7 8 12 50

output:
2
"""

import sys


def solve():
    rec[0] = 0
    for i in range(c_num):
        for j in range(money - coins[i] + 1):
            rec[j + coins[i]] = min(rec[j + coins[i]], rec[j] + 1)

    return rec


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    money, c_num = map(int, _input[0].split())
    coins = list(map(int, _input[1].split()))
    assert len(coins) == c_num
    rec = [float('inf')] * (money + 1)
    ans = solve()
    print(ans[-1])

Submission status: Accepted

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

"""
input:
15 6
1 2 7 8 12 50

output:
2
"""

import sys


def solve():
    rec[0] = 0
    for i in range(c_num):
        for j in range(coins[i], money + 1):
            rec[j] = min(rec[j], rec[j - coins[i]] + 1)

    return rec


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    money, c_num = map(int, _input[0].split())
    coins = list(map(int, _input[1].split()))
    # assert len(coins) == c_num
    rec = [float('inf')] * (money + 1)
    ans = solve()
    print(ans.pop())

Submission status: Accepted

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

"""
input:
15 6
1 2 7 8 12 50

output:
2
"""

import sys


def solve():
    rec[0] = 0
    for i in range(all_coins):
        for j in range(coins[i], money + 1):
            rec[j] = min(rec[j], rec[j - coins[i]] + 1)

    return rec


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    money, all_coins = map(int, _input[0].split())
    coins = list(map(int, _input[1].split()))
    # assert len(coins) == c_num
    rec = [float('inf')] * (money + 1)
    ans = solve()
    print(ans.pop())

Submission status: Accepted

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

"""
input:
15 6
1 2 7 8 12 50

output:
2
"""

import sys


def solve():
    rec[0] = 0
    for coin in coins:
        for current_cost in range(coin, total_cost + 1):
            rec[current_cost] = min(rec[current_cost], rec[current_cost - coin * 1] + 1)

    return rec


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    total_cost, c_num = map(int, _input[0].split())
    coins = list(map(int, _input[1].split()))
    # assert len(coins) == c_num
    rec = [float('inf')] * (total_cost + 1)
    ans = solve()
    print(ans[-1])

Submission status: Accepted

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

"""
input:
15 6
1 2 7 8 12 50

output:
2
"""

import sys


def solve():
    rec[0] = 0
    for coin in coins:
        for current_cost in range(coin, total_cost + 1):
            rec[current_cost] = min(rec[current_cost], rec[current_cost - coin] + 1)

    return rec


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    total_cost, c_num = map(int, _input[0].split())
    coins = list(map(int, _input[1].split()))
    # assert len(coins) == c_num
    rec = [float('inf')] * (total_cost + 1)
    ans = solve()
    print(ans.pop())

Submission status: Accepted

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

minimum = [50000] * (n+1)
minimum[0] = 0

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

print(minimum[n])

Submission status: Accepted

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

minimum = [50000] * (n+1)
minimum[0] = 0

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

print(minimum[n])

Submission status: Accepted

Solution code:
n = int(input().split()[0])
c = list(filter(lambda x:x <= n,map(int,input().split())))
m = len(c)

minimum = [n] * (n+1)
minimum[0] = 0
for i in c:
    minimum[i] = 1

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

print(minimum[n])

Submission status: Accepted

Solution code:
n = int(input().split()[0])
c = list(filter(lambda x:x <= n,map(int,input().split())))
m = len(c)

minimum = [ i for i in range(n+1) ]
for i in c:
    minimum[i] = 1

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

print(minimum[n])

Submission status: Accepted

Solution code:
n = int(input().split()[0])
c = list(filter(lambda x:x <= n,map(int,input().split())))
m = len(c)

minimum = [ i for i in range(n+1) ]
for i in c:
    minimum[i] = 1

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

print(minimum[n])

Submission status: Accepted

Solution code:
n = int(input().split()[0])
c = list(filter(lambda x:x <= n,map(int,input().split())))

minimum = [ i for i in range(n+1) ]
for i in c:
    minimum[i] = 1

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

print(minimum[n])

Submission status: Accepted

Solution code:
n = int(input().split()[0])
c = sorted(filter(lambda x:x <= n,map(int,input().split())))

minimum = [ i for i in range(n+1) ]
for i in c:
    minimum[i] = 1

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

print(minimum[n])

Submission status: Accepted

Solution code:
n = int(input().split()[0])
c = list(filter(lambda x:x <= n,map(int,input().split())))

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

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

print(minimum[n])

Submission status: Accepted

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

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

print(minimum[n])

Submission status: Accepted

Solution code:
m,n=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
dp=[[int(1e4) for i in range(m+1)] for j in range(n+1)]
i=n-1
while i>=0:
    for j in range(m+1):
        if j==c[i]:
            dp[i][j]=1
        elif j<c[i]:
            dp[i][j]=dp[i+1][j]
        else:
            dp[i][j]=min(dp[i+1][j],dp[i+1][j-c[i]]+1,dp[i][j-c[i]]+1)
    i-=1
print(dp[0][m])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

INF = 1000000000

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

Submission status: Accepted

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

INF = float("inf")
dp = [INF for i in xrange(n + 1)]
dp[0] = 0
for i in xrange(1, n + 1):
    for j in xrange(m):
        if c[j] <= i:
            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 = sorted(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[n])

Submission status: Accepted

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

import sys
import os
import pprint

#fd = os.open('DPL_1_A.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

# n: n???????????????
# m: m?¨????????????????
n, m = list(map(int, input().split()))
C = list(map(int, input().split()))
MAX = 50000

# i???????????§????????????????????£???j????????????????°??????°
# T[i][j]
# m * (MAX + 1) ?¬????
T = [[float('inf') for i in range(MAX + 1)] for j in range(m)]

#print(n, '???????????????')
for i in range(0, m):
    T[i][0] = 0
    for j in range(1, n + 1):
        #print('i', i, 'j', j, 'C[i]', C[i], 'T[i,j]', T[i][j])
        if C[i] <= n:
            T[i][j] = min(T[i-1][j], T[i][j - C[i]] + 1)
        else:
            T[i][j] = T[i - 1][j]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def coin_change(coins, payment):
    T = [0] + [50001] * payment
    for c in coins:
        for i in range(c, payment + 1):
            T[i] = min(T[i], T[i - c] + 1)
    return T[payment]

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

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

ans = coin_change(c, n)

print(ans)

Submission status: Accepted

Solution code:
def coin_change(coins, payment):
    T = [0] + [50001] * payment
    for c in coins:
        for i, t in enumerate(zip(T[c:], T), start=c):
            a, b = t
            T[i] = min(a, b + 1)
    return T[payment]

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

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

ans = coin_change(c, n)

print(ans)

Submission status: Accepted

Solution code:
INF = 100 ** 7


def main():
    n, m = map(int, input().split())
    c_list = list(map(int, input().split()))

    dp = [INF] * (n + 1)
    dp[0] = 0
    for c in c_list:
        for i in range(len(dp)):
            if dp[i] != INF and i + c < len(dp):
                dp[i + c] = min(dp[i + c], dp[i] + 1)
    print(dp[n])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
C = list(map(int, input().split()))
inf = float("inf")
T = [inf for i in range(n+1)]
T[0] = 0

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

print(str(T[n]))

Submission status: Accepted

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

currency = sorted(map(int,input().split()))

gra = [float('inf')]*(n+1)
gra[0] = 0
for i in range(m):
    for j in range(currency[i],n+1):
        gra[j] = min(gra[j],gra[j-currency[i]]+1)

print(gra[n])