Problem:
Coin Changing Problem Find the minimum number of coins to make change for n cents using coins of denominations d 1 , d 2 ,.., d m . The coins can be used any number of times. Input  n  m  d 1  d 2 ... d m  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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Solution (Python):

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]

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

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

Solution (Python):



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

Solution (Python):



"""
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()))
    
    rec = [float('inf')] * (money + 1)
    ans = solve()
    print(ans.pop())

Solution (Python):



"""
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()))
    
    rec = [float('inf')] * (money + 1)
    ans = solve()
    print(ans.pop())

Solution (Python):



"""
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()))
    
    rec = [float('inf')] * (total_cost + 1)
    ans = solve()
    print(ans[-1])

Solution (Python):



"""
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()))
    
    rec = [float('inf')] * (total_cost + 1)
    ans = solve()
    print(ans.pop())

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Solution (Python):


import sys
import os
import pprint






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




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


for i in range(0, m):
    T[i][0] = 0
    for j in range(1, n + 1):
        
        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])

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

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

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

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

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

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

Solution (Python):
import sys

inf = 1<<30

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

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

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

    ans = dp[n]
    print(ans)

if __name__ == '__main__':
    solve()

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

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

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

Solution (Python):
n, m = map(int, input().split())
c = list(map(int, input().split()))
dp = [float("inf")]*(n+1)
dp[0] = 0
for i in range(m):
    for j in range(c[i], n+1):
        dp[j] = dp[j - c[i]]+1 if dp[j - c[i]] < dp[j] else dp[j]
print(dp[n])

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



if __name__ == '__main__':
    
    
    
    

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

    
    result = calc_number_of_coin(sum, coins)

    
    print(result)

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


if __name__ == '__main__':
    
    
    
    

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

    
    result = calc_number_of_coin(sum, coins)

    
    print(result)

Solution (Python):

N, M = tuple(map(int, input().split()))
coins = sorted(tuple(map(int, input().split())))

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

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

print(counts[-1])

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

INF = 10**12

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

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

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

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

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

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

INF = 10**12

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

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

print(T[n])

Solution (Python):
import sys


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

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

    return T[n]


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

print(getTheNumberOfCoin(n, m, c))

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

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

print(dp[n])

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

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

print(dp[n])

Solution (Python):
def calc_t(i,j):
    global t,c
    if i<0 or j<0:
        return n+2
    
    if t[i][j]==n+1:
        t[i][j]=min(calc_t(i-1,j),calc_t(i,j-c[i])+1)
    return t[i][j]

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


for a in range(n+1):
    for b in range(m):
        calc_t(b,a)
print(calc_t(m-1,n))

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


T = [0] + [float('inf')] * n

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

print(T[-1])

Solution (Python):


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

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

print(f[n])

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

if __name__=="__main__":
    main()

Solution (Python):



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

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

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

print dp[n]

Solution (Python):

def inpl(): return list(map(int, input().split()))
n, m = inpl()
C = sorted(inpl())
DP = list(range(n+1))

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

Solution (Python):



if __name__ == '__main__':
    n, m = map(int, input().split())
    C = [int(x) for x in input().split()]
    T = [float("inf") for _ in range(n+1)]
    T[0] = 0

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

    print(T[n])

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

print(dp[-1])

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


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

Solution (Python):

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

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

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

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

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

c.remove(1)
c.sort()

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

print dp[n]

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


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

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

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

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

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

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

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

    print(dp[n])
main()

Solution (Python):

"""
Created on Sat May 26 12:16:54 2018
DPL-1A Rec Call Revised
@author: maezawa
"""

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




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

print(dp[n])

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