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

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

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

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

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

print(dp[n])

Solution (Python):


import sys

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

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

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

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

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

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

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

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

print(dp[n])

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

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

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

print(dp[n])

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

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

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

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

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

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

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

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

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

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

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

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

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):
N,M = map(int, input().split())
C= list(map(int, input().split()))
inf = float("inf")

dp =  [inf] * (N+1)

dp[0] = 0

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

print(dp[N])

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

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

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

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

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

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


print(dp[n])

Solution (Python):



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

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

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

print (dp[n])

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

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

Solution (Python):
class DP2D(object):

    def __init__(self, item_n: int, border: int, initializer: int = 0):
        self.item_n = item_n
        self.border = border
        self.table = [[initializer for _ in range(self.item_n + 1)] for _ in range(self.border + 1)]

    def __str__(self):
        return "\n".join(list(map(lambda l:
                                  " ".join(list(map(str, l)))
                                  , self.table)))

    def __repr__(self):
        return "DynamicProgramming object:\n" + \
               "item_n: " + str(self.item_n) + ", border: " + str(self.border) + "\n" + \
               "table:\n" + self.__str__()

    def solve(self, expr: callable) -> list:
        raise NotImplementedError

    def fill_0_idx_with(self, value: int) -> "DP2D":
        self.table[0] = [value for _ in range(self.item_n + 1)]
        for i in range(1, self.border + 1):
            self.table[i][0] = value
        return self


class DP2DOptimizer(DP2D):

    def __init__(self, item_n: int, border: int, obj_coef: list, sbj_coef: list, initializer: int = 0):
        super(DP2DOptimizer, self).__init__(item_n, border, initializer=initializer)

        if len(obj_coef) == self.item_n:  
            obj_coef = [0] + obj_coef
        self.obj_coef = obj_coef

        if len(sbj_coef) == self.item_n:
            sbj_coef = [0] + sbj_coef
        self.sbj_coef = sbj_coef

    def solve(self, expr: callable) -> list:
        for weight_lim in range(1, self.border + 1):
            for item_idx in range(1, self.item_n + 1):
                self.table[weight_lim][item_idx] = expr(weight_lim, item_idx)

        return self.table

    def coin_expr(self, target, coin_idx) -> int:
        if self.sbj_coef[coin_idx] == 1:
            res = target
        else:
            res = self.table[target][coin_idx - 1]
            if target - self.sbj_coef[coin_idx] >= 0:
                res = min(res, self.table[target - self.sbj_coef[coin_idx]][coin_idx] + self.obj_coef[coin_idx])
        return res


if __name__ == '__main__':
    n, m = map(int, input().split())
    values = [int(i) for i in input().split()]
    dp = DP2DOptimizer(m, n, [1 for _ in range(m)], values, 50000).fill_0_idx_with(0)
    print(dp.solve(dp.coin_expr)[n][m])

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

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

print(dp[n])

Solution (Python):
iipt=lambda:int(input())
miipt=lambda:list(map(int,input().split(" ")))

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

Solution (Python):





import sys
input = sys.stdin.readline



def Reflection(p1,p2):
    (x,y) = p2
    (tx,ty) = Projection(p1,(x,y))
    rx = (tx - x) * 2 + x 
    ry = (ty - y) * 2 + y
    return (rx,ry)


def solve(cn:int,l:list):
    calc = [[0 for i in range(len(l))] for j in range(cn+1)]
    calc[0][0] = 0

    for i in range(cn+1):
        calc[i][0] = i // l[0] if i % l[0] == 0 else (i // l[0]) + 1

    for j in range(1,len(l)):
        for i in range(cn+1):
            if i-l[j] >= 0:
                calc[i][j] = min(calc[i][j-1],calc[i-l[j]][j]+1)
            else:
                calc[i][j] = calc[i][j-1]
    print (calc[cn][j])
    return 0

def main():
    (cn,n) = map(int,input().split())
    l = list(map(int,input().split()))

    solve(cn,l)
    
if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
ds = list(map(int, input().split()))
ds = sorted(ds)
dp = [100000] * (n+1)
dp[0] = 0

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

print(dp[n])

Solution (Python):




def change(n, cs):
    ts = [[0] * (n+1) for _ in range(len(cs)+1)]
    for j in range(0, n+1):
        ts[0][j] = n+1

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

    return ts[-1][-1]


def run():
    n, m = [int(i) for i in input().split()]
    denoms = [int(i) for i in input().split()]

    print(change(n, denoms))


if __name__ == '__main__':
    run()

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


def get_coin_number(coin_list, n, m):
    t = [float("inf") for i in range(n + 1)]
    t[0] = 0

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


print(get_coin_number(c_list, n, m))

Solution (Python):



n, m = [int(t) for t in input().split()]
c    = [int(t) for t in input().split()]
assert len(c) == m


ncoin = {0: 0}

for k in range(1, n + 1):
    ncoin[k] = min(ncoin[k - x] + 1 for x in c if k >= x)

print(ncoin[n])

Solution (Python):
BIG_NUM = 10**9

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

l = [BIG_NUM] * (n+1)
l[0] = 0

for c_i in c:
	for j in range(1, n+1):
		if j < c_i:
			continue
		l[j] = min(l[j-c_i]+1, l[j])

	
print(l[n])

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

data=[0,1]
for i in range(2,n+1):
    mini=i
    for coin in coins:
        if i-coin>=0:
            if data[i-coin]<mini:
                mini=data[i-coin]
    data.append(mini+1)
print(data[n])

Solution (Python):
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
 

 
BIG_NUM = 2000000000
HUGE_NUM = 9999999999999999
MOD = 1000000007
EPS = 0.000000001
 

 
W,N = map(int,input().split())
 
table = [BIG_NUM]*(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]))

Solution (Python):
n, m = map(int, input().strip().split())
d = [i for i in map(int, input().strip().split())]
assert len(d) == m

cands = sorted(d)
data = [i for i in range(n+1)]

for c in cands:
    for i in range(n+1):
        if i + c <= n and data[i+c] > data[i] + 1:
            data[i+c] = data[i] + 1
print(data[-1])

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

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

Solution (Python):
n, m = map(int, input().split())
C = list(map(int, input().split()))
T = [0]+[float('inf')]*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[j])

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

Solution (Python):
N, m = map(int, input().split())
mlist = sorted(list(map(int, input().split())))

ilist = [i for i in range(N+1)] 

for i in range(m-1):  
    cm = mlist[i+1]
    copy1 = ilist[:]   
    for k in range(1,N+1):    
        if (cm > k):
            ilist[k] = copy1[k]
        else:
            ilist[k] = min(copy1[k], (ilist[k-cm] + 1))
print(ilist[-1])

Solution (Python):
def getTheNumberOfCoin(n, m, c):
    INF = 1 << 29
    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)

    return t[n]

if __name__ == '__main__':
    n, m = [int(v) for v in input().split()]
    c = [int(v) for v in input().split()]
    print(getTheNumberOfCoin(n, m, c))

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

coins = map(int,raw_input().split())

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

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

print dp[n]

Solution (Python):
n,m=map(int,input().split(" "))
c=sorted(list(map(int,input().split(" "))))[1:]
ans=list(range(n+1))
for i in c:
    for j in range(i,n+1):
        ans[j]=min([ans[j],(ans[j-i]+1)])
print(ans[-1])

Solution (Python):
import sys
def get_min_no_of_coins(p, coins):
	dp = [sys.maxsize-1] * (p+1)
	dp[0] = 0
	for coin in coins:
		for i in range(coin, p+1):
			dp[i] = min(dp[i], dp[i-coin]+1)
	return dp[p]

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

ans = get_min_no_of_coins(p, coins)
print(ans)

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

Solution (Python):


MAX = 50005

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


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

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

print(dp[n])