Given a list of coins of distinct denominations and total amount of money. Find the minimum number of coins required to make up that amount. Output -1 if that money cannot be made up using given coins.
You may assume that there are infinite numbers of coins of each type.
 
Example 1:
Input: arr = [1, 2, 5], amount = 11
Output: 3
Explanation: 2*5 + 1 = 11. So taking 2 
denominations of 5 and 1 denomination of  
1, one can make 11.
Example 2:
Input: arr = [2, 6], amount = 7
Output: -1
Explanation: Not possible to make 7 using 
denominations 2 and 6.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function MinCoin() which takes list of denominations and amount as input parameter and returns miimum number of coins to make up amount. If not possible returns -1.
 
Expected Time Complexity: O(n*amount)
Expected Space Complexity: O(amount)
 
Contstraints:
1 <= number of distinct denominations <= 100
1 <= amount <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

	def MinCoin(self, nums, amount):

		# Code here

Solutions:
class Solution:

	def MinCoin(self, nums, W):
		import sys
		sys.setrecursionlimit(10 ** 9 + 7)
		n = len(nums)
		prev = [sys.maxsize for j in range(W + 1)]
		curr = [sys.maxsize for j in range(W + 1)]
		for j in range(W + 1):
			if j % nums[0] == 0:
				prev[j] = j // nums[0]
		for i in range(1, n):
			for j in range(W + 1):
				pick = sys.maxsize
				npick = prev[j]
				if nums[i] <= j:
					pick = 1 + curr[j - nums[i]]
				curr[j] = min(pick, npick)
			prev = curr
		if prev[amount] != sys.maxsize:
			return prev[amount]
		return -1

	def solve(self, n, W, nums, dp):
		import sys
		if n == 0:
			if W % nums[n] == 0:
				dp[n][W] = W // nums[n]
				return dp[n][W]
			dp[n][W] = sys.maxsize
			return sys.maxsize
		if dp[n][W] != sys.maxsize:
			return dp[n][W]
		npick = self.solve(n - 1, W, nums, dp)
		pick = sys.maxsize
		if nums[n] <= W:
			pick = 1 + self.solve(n, W - nums[n], nums, dp)
		dp[n][W] = min(dp[n][W], min(pick, npick))
		return dp[n][W]


import sys

class Solution:

	def mcoins(self, coins, x, n, dp):
		if x == 0:
			return 0
		if x < 0:
			return sys.maxsize
		if dp[x] != -1:
			return dp[x]
		mini = sys.maxsize
		for i in range(n):
			ans = self.mcoins(coins, x - coins[i], n, dp)
			if ans != sys.maxsize:
				mini = min(ans + 1, mini)
		dp[x] = mini
		return mini

	def solve(self, coins, x):
		dp = [sys.maxsize for _ in range(x + 1)]
		dp[0] = 0
		for i in range(1, x + 1):
			for j in range(len(coins)):
				if i - coins[j] >= 0 and dp[i - coins[j]] != sys.maxsize:
					dp[i] = min(dp[i], 1 + dp[i - coins[j]])
		if dp[x] == sys.maxsize:
			return -1
		return dp[x]

	def MinCoin(self, nums, amount):
		a = self.solve(nums, amount)
		return a


class Solution:

	def MinCoin(self, nums, amount):
		dp = [float('inf') for _ in range(amount + 1)]
		dp[0] = 0
		for i in range(len(dp)):
			for j in nums:
				if i - j >= 0:
					dp[i] = min(dp[i], dp[i - j] + 1)
		return -1 if dp[-1] == float('inf') else dp[-1]


class Solution:

	def MinCoin(self, coins, amount):
		dp = [amount + 1 for i in range(0, amount + 1)]
		dp[0] = 0
		for i in range(1, len(dp)):
			for coin in coins:
				if coin <= i:
					dp[i] = min(1 + dp[i - coin], dp[i])
		return -1 if dp[amount] == amount + 1 else dp[amount]


class Solution:

	def noofways(self, amt, coins, n, dp):
		if amt == 0:
			return 0
		if n == 0:
			return float('inf')
		if n == 1 and amt > 1:
			if amt % coins[n - 1] == 0:
				return amt // coins[n - 1]
			else:
				return float('inf')
		if dp[n][amt] != -1:
			return dp[n][amt]
		if coins[n - 1] > amt:
			dp[n][amt] = self.noofways(amt, coins, n - 1, dp)
			return dp[n][amt]
		else:
			dp[n][amt] = min(1 + self.noofways(amt - coins[n - 1], coins, n, dp), self.noofways(amt, coins, n - 1, dp))
			return dp[n][amt]

	def MinCoin(self, nums, amount):
		coins = nums
		dp = [[-1 for _ in range(amount + 1)] for _ in range(len(coins) + 1)]
		if self.noofways(amount, coins, len(coins), dp) == float('inf'):
			return -1
		else:
			return self.noofways(amount, coins, len(coins), dp)


class Solution:

	def MinCoin(self, arr, amount):
		dp = [0] * (amount + 1)
		arr.sort()
		for amt in range(1, amount + 1):
			ans = float('INF')
			for coin in arr:
				if coin <= amt:
					ans = min(ans, 1 + dp[amt - coin])
				else:
					break
			dp[amt] = ans
		if dp[amount] >= 10 ** 9 + 7:
			return -1
		else:
			return dp[amount]


class Solution:

	def MinCoin(self, arr, amount):
		dp = {}
		arr.sort()

		def solve(amt):
			if amt == 0:
				return 0
			elif amt in dp:
				return dp[amt]
			else:
				ans = float('INF')
				for val in arr:
					if val <= amt:
						ans = min(ans, 1 + solve(amt - val))
					else:
						break
				dp[amt] = ans
				return ans
		val = solve(amount)
		if val >= 10 ** 9 + 7:
			return -1
		else:
			return val


class Solution:

	def MinCoin(self, arr, amount):
		N = len(arr)
		dp = {}
		arr.sort(reverse=True)

		def solve(n, amt):
			if amt == 0:
				return 0
			elif n == 0:
				return float('INF')
			elif (n, amt) in dp:
				return dp[n, amt]
			else:
				val = arr[n - 1]
				if val <= amt:
					c1 = 1 + solve(n, amt - val)
					c2 = solve(n - 1, amt)
					c = min(c1, c2)
				else:
					c = float('INF')
				dp[n, amt] = c
				return c
		val = solve(N, amount)
		if val >= 10 ** 9 + 7:
			return -1
		else:
			return val


class Solution:

	def MinCoin(self, nums, amount):
		n = len(nums)
		nums.sort()
		dp = [1000000000000.0] * (amount + 1)
		dp[0] = 0
		for i in range(1, amount + 1):
			for j in range(n):
				if nums[j] > i:
					break
				dp[i] = min(dp[i], 1 + dp[i - nums[j]])
		if dp[amount] == 1000000000000.0:
			return -1
		return dp[amount]


def dynamic(arr, amount):
	n = len(arr)
	arr.sort()
	arr = arr[::-1]
	dp = [[10 ** 5 for _ in range(amount + 1)] for _ in range(n + 1)]
	for i in range(n + 1):
		dp[i][0] = 1
	for i in range(1, n + 1):
		for j in range(1, amount + 1):
			if j % arr[i - 1] == 0:
				dp[i][j] = j // arr[i - 1]
	for i in range(1, n + 1):
		for j in range(1, amount + 1):
			if j >= arr[i - 1]:
				dp[i][j] = min(dp[i][j], dp[i][j - arr[i - 1]] + dp[i][arr[i - 1]], dp[i - 1][j])
			else:
				dp[i][j] = dp[i - 1][j]
	if dp[n][amount] == 10 ** 5:
		return -1
	return dp[n][amount]

class Solution:

	def MinCoin(self, nums, amount):
		return dynamic(nums, amount)


class Solution:

	def MinCoin(self, nums, amount):

		def func(coins, ind, tar, dp):
			if ind == 0:
				if tar % coins[ind] == 0:
					return tar // coins[ind]
				else:
					return 10 ** 9
			if dp[ind][tar] != -1:
				return dp[ind][tar]
			nottake = 0 + func(coins, ind - 1, tar, dp)
			take = 10 ** 9
			if coins[ind] <= tar:
				take = 1 + func(coins, ind, tar - coins[ind], dp)
			dp[ind][tar] = min(nottake, take)
			return dp[ind][tar]
		n = len(nums)
		dp = [[-1 for i in range(amount + 1)] for j in range(n)]
		kk = func(nums, n - 1, amount, dp)
		if kk == 10 ** 9:
			return -1
		return kk


class Solution:

	def MinCoin(self, coins, total_amount):
		min_coin_results = [-2] * total_amount
		for coin in coins:
			if coin <= total_amount:
				min_coin_results[coin - 1] = 1
		return self.MinCoinHelper(coins, total_amount, min_coin_results)

	def MinCoinHelper(self, coins, total_amount, min_coin_results):
		if total_amount == 0:
			return 0
		if min_coin_results[total_amount - 1] != -2:
			return min_coin_results[total_amount - 1]
		result = -1
		for coin in coins:
			if total_amount >= coin:
				temp_result = self.MinCoinHelper(coins, total_amount - coin, min_coin_results)
				if temp_result >= 0 and (result == -1 or result >= temp_result + 1):
					result = temp_result + 1
		min_coin_results[total_amount - 1] = result
		return result


class Solution:

	def MinCoin(self, nums, amount):
		N = len(nums)
		nums.sort()
		dp = {}

		def solve(amt):
			if amt == 0:
				return 0
			elif amt in dp:
				return dp[amt]
			else:
				ans = float('INF')
				for coin in nums:
					if coin <= amt:
						ans = min(ans, 1 + solve(amt - coin))
					else:
						break
				dp[amt] = ans
				return ans
		val = solve(amount)
		if val > 10 ** 9 + 7:
			return -1
		else:
			return val


class Solution:

	def MinCoin(self, nums, amount):
		N = len(nums)
		nums.sort(reverse=True)
		dp = {}

		def solve(n, cap):
			if cap == 0:
				return 0
			elif n == 0:
				return float('INF')
			elif (n, cap) in dp:
				return dp[n, cap]
			else:
				cv = nums[n - 1]
				if cv <= cap:
					c1 = 1 + solve(n, cap - cv)
					c2 = solve(n - 1, cap)
					c = min(c1, c2)
				else:
					c = float('INf')
				dp[n, cap] = c
				return c
		val = solve(N, amount)
		if val >= 10 ** 9 + 7:
			return -1
		else:
			return val


class Solution:

	def MinCoin(self, coins, target):
		dp = [[0 for i in range(target + 1)] for i in range(len(coins))]
		for i in range(target + 1):
			if i % coins[0] == 0:
				dp[0][i] = i // coins[0]
			else:
				dp[0][i] = 1000000000.0
		for i in range(1, n):
			for j in range(target + 1):
				nottake = dp[i - 1][j]
				take = 1000000000.0
				if coins[i] <= j:
					take = 1 + dp[i][j - coins[i]]
				dp[i][j] = min(take, nottake)
		if dp[n - 1][target] >= 1000000000.0:
			return -1
		return dp[n - 1][target]


class Solution:

	def MinCoin(self, nums, amount):
		(n, x) = (len(nums), amount)
		c = nums
		a = [-1 for i in range(x + 1)]
		a[0] = 0
		for i in range(x):
			if a[i] != -1:
				for j in c:
					if i + j <= x:
						if a[i + j] == -1:
							a[i + j] = a[i] + 1
						a[i + j] = min(a[i + j], a[i] + 1)
		return a[-1]


class Solution:

	def fun(self, idx, arr, target, dp):
		if idx == 0:
			if target % arr[0] == 0:
				return target // arr[0]
			else:
				return float('inf')
		if dp[idx][target] != -1:
			return dp[idx][target]
		np = 0 + self.fun(idx - 1, arr, target, dp)
		p = float('inf')
		if arr[idx] <= target:
			p = 1 + self.fun(idx, arr, target - arr[idx], dp)
		dp[idx][target] = min(np, p)
		return dp[idx][target]

	def MinCoin(self, arr, target):
		n = len(arr)
		dp = [[-1 for i in range(target + 1)] for j in range(n)]
		ans = self.fun(n - 1, arr, target, dp)
		if ans == float('inf'):
			return -1
		else:
			return ans


class Solution:

	def MinCoin(self, nums, amount):
		n = len(nums)
		dp = [[0 for i in range(amount + 1)] for j in range(n)]
		for i in range(amount + 1):
			if i % nums[0] == 0:
				dp[0][i] = i // nums[0]
			else:
				dp[0][i] = 1000000000.0
		for ind in range(1, n):
			for amount in range(amount + 1):
				not_take = dp[ind - 1][amount]
				take = 1000000000.0
				if nums[ind] <= amount:
					take = 1 + dp[ind][amount - nums[ind]]
				dp[ind][amount] = min(take, not_take)
		ans = dp[n - 1][amount]
		if ans >= 1000000000.0:
			return -1
		else:
			return ans


class Solution:

	def MinCoin(self, nums, amount):
		N = len(nums)
		dp = {}

		def solve(n, amt):
			if amt == 0:
				return 0
			if n == 0:
				return float('INF')
			elif (n, amt) in dp:
				return dp[n, amt]
			else:
				item = nums[n - 1]
				if item <= amt:
					c1 = 1 + solve(n, amt - item)
					c2 = solve(n - 1, amt)
					c = min(c1, c2)
				else:
					c = solve(n - 1, amt)
				dp[n, amt] = c
				return c
		val = solve(N, amount)
		if val >= 10 ** 9 + 7:
			return -1
		else:
			return val


class Solution:

	def MinCoin(self, nums, amount):
		dp = [[-1 for i in range(amount + 1)] for i in range(len(nums))]

		def f(ind, arr, target, dp):
			if ind == 0:
				if target % arr[ind] == 0:
					return target // arr[ind]
				else:
					return 1000000000.0
			if dp[ind][target] != -1:
				return dp[ind][target]
			not_pic = 0 + f(ind - 1, arr, target, dp)
			pic = 1000000000.0
			if arr[ind] <= target:
				pic = 1 + f(ind, arr, target - arr[ind], dp)
			dp[ind][target] = min(pic, not_pic)
			return dp[ind][target]
		ans = f(len(nums) - 1, nums, amount, dp)
		if ans == 1000000000.0:
			return -1
		else:
			return ans


class Solution:

	def MinCoin(self, nums, amount):
		n = len(nums)
		dp = [[10000000000 for i in range(amount + 1)] for i in range(n)]
		for i in range(n):
			dp[i][0] = 0
		for i in range(1, amount + 1):
			if nums[0] <= i:
				dp[0][i] = dp[0][i - nums[0]] + 1
		for i in range(1, n):
			for j in range(1, amount + 1):
				dp[i][j] = dp[i - 1][j]
				if nums[i] <= j:
					dp[i][j] = min(dp[i][j], dp[i][j - nums[i]] + 1)
		ans = dp[n - 1][amount]
		if ans >= 10000000000:
			return -1
		return ans


class Solution:

	def MinCoin(self, nums, amount):
		dp = [-1] * (amount + 1)
		dp[0] = 0
		for i in range(1, amount + 1):
			ans = 9999999
			for el in nums:
				f = i - el
				if f >= 0:
					par_ans = 1 + dp[f]
					ans = min(par_ans, ans)
			dp[i] = ans
		if dp[amount] == 9999999:
			return -1
		return dp[amount]


class Solution:

	def MinCoin(self, nums, amount):

		def find(nums, amount, dp):
			if amount == 0:
				return 0
			if amount < 0:
				return 9999999
			if dp[amount] != -1:
				return dp[amount]
			ans = 9999999
			for el in nums:
				par_ans = 1 + find(nums, amount - el, dp)
				ans = min(par_ans, ans)
			dp[amount] = ans
			return dp[amount]
		dp = [-1] * (amount + 1)
		ans = find(nums, amount, dp)
		if ans == 9999999:
			return -1
		return ans


class Solution:

	def MinCoin(self, nums, amount):
		dp = [amount + 1] * 100001
		dp[0] = 0
		for i in range(len(nums)):
			for j in range(1, amount + 1):
				if nums[i] <= j:
					dp[j] = min(dp[j], dp[j - nums[i]] + 1)
		if dp[amount] > amount:
			return -1
		return dp[amount]


class Solution:

	def MinCoin(self, nums, amount):
		n = len(nums)
		k = [[0 for i in range(amount + 1)] for i in range(n + 1)]
		for j in range(amount + 1):
			k[0][j] = float('inf')
		for i in range(1, n + 1):
			k[i][0] = 0
		for i in range(1, n + 1):
			if amount % nums[i - 1] == 0:
				k[i][amount] = amount // nums[i - 1]
			else:
				k[i][amount] = float('inf')
		for i in range(1, n + 1):
			for j in range(1, amount + 1):
				if nums[i - 1] <= j:
					k[i][j] = min(k[i - 1][j], 1 + k[i][j - nums[i - 1]])
				else:
					k[i][j] = k[i - 1][j]
		return k[n][amount] if k[n][amount] != float('inf') else -1


from collections import defaultdict

class Solution:

	def MinCoin(self, nums, amount):
		d = defaultdict(lambda : float('inf'))
		d[0] = 0
		for i in range(1, amount + 1):
			mini = float('inf')
			for j in range(len(nums)):
				mini = min(mini, d[i - nums[j]] + 1)
			d[i] = mini
		return d[amount] if d[amount] <= amount else -1


import sys

class Solution:

	def MinCoin(self, nums, amount):
		dp = [-1] * (amount + 1)
		dp[0] = 0
		for i in nums:
			if i <= amount:
				dp[i] = 1
		for j in range(amount + 1):
			if dp[j] != -1:
				for k in nums:
					if j + k <= amount:
						if dp[j + k] == -1:
							dp[j + k] = dp[j] + 1
						else:
							dp[j + k] = min(dp[j + k], dp[j] + 1)
		return dp[amount]


class Solution:

	def MinCoin(self, nums, amount):
		coins = nums
		V = amount
		m = max(coins)
		m = max(m, V)
		dp = [-1] * (m + 1)
		for el in coins:
			dp[el] = 1
		for i in range(V + 1):
			choices = []
			for el in coins:
				if i == el:
					choices.append(1)
				elif i - el >= 0 and dp[i - el] != -1:
					choices.append(dp[i - el] + 1)
			if len(choices) > 0:
				dp[i] = min(choices)
		return dp[V]


class Solution:

	def MinCoin(self, coins, amount):
		n = len(coins)
		dp = [[0 for j in range(0, amount + 1)] for i in range(0, n + 1)]
		for i in range(0, n + 1):
			dp[i][0] = 0
		for j in range(1, amount + 1):
			if j % coins[0] == 0:
				dp[1][j] = j // coins[0]
			else:
				dp[1][j] = 1000000000.0
		for i in range(2, n + 1):
			for j in range(1, amount + 1):
				if coins[i - 1] > j:
					dp[i][j] = dp[i - 1][j]
				else:
					include = 1 + dp[i][j - coins[i - 1]]
					exclude = dp[i - 1][j]
					dp[i][j] = min(include, exclude)
		if dp[n][amount] >= 1000000000.0:
			return -1
		return dp[n][amount]


class Solution:

	def MinCoin(self, nums, amount):
		prev = [0] * (amount + 1)
		cur = [0] * (amount + 1)
		for T in range(amount + 1):
			if T % nums[0] == 0:
				prev[T] = T // nums[0]
			else:
				prev[T] = float('inf')
		for ind in range(1, len(nums)):
			for target in range(amount + 1):
				notTake = 0 + prev[target]
				take = float('inf')
				if nums[ind] <= target:
					take = 1 + cur[target - nums[ind]]
				cur[target] = min(take, notTake)
			prev = cur
		res = prev[amount]
		if res >= float('inf'):
			return -1
		return res


class Solution:

	def f(self, ind, target, arr, dp):
		if ind == 0:
			if target % arr[ind] == 0:
				return target // arr[ind]
			else:
				return float('inf')
		if dp[ind][target] != -1:
			return dp[ind][target]
		notTake = 0 + self.f(ind - 1, target, arr, dp)
		take = float('inf')
		if arr[ind] <= target:
			take = 1 + self.f(ind, target - arr[ind], arr, dp)
		dp[ind][target] = min(take, notTake)
		return min(take, notTake)

	def MinCoin(self, nums, amount):
		dp = [[-1 for _ in range(amount + 1)] for _ in range(len(nums))]
		res = self.f(len(nums) - 1, amount, nums, dp)
		if res == float('inf'):
			return -1
		return res


class Solution:

	def MinCoin(self, nums, amount):
		d = dict()
		res = self.MinCoiN(nums, amount, d)
		if res == float('inf'):
			return -1
		return res

	def MinCoiN(self, nums, amount, d):
		if amount in d:
			return d[amount]
		if amount == 0:
			return 0
		if amount < 0:
			return -1
		else:
			Max = float('inf')
			for i in nums:
				x = self.MinCoiN(nums, amount - i, d)
				if x != -1 and x != float('inf'):
					x = x + 1
					if x < Max:
						Max = x
		d[amount] = Max
		return Max


class Solution:

	def MinCoin(self, a, n):
		dp = [float('inf')] * (n + 1)
		dp[0] = 0
		for i in range(1, n + 1):
			for j in a:
				if i - j >= 0:
					dp[i] = min(dp[i - j] + 1, dp[i])
		if dp[n] == float('inf'):
			return -1
		return dp[n]


class Solution:

	def help(self, nums, amt, n):
		dp = [[0 for j in range(amt + 1)] for i in range(n + 1)]
		for i in range(amt + 1):
			dp[0][i] = float('inf')
		for i in range(1, n + 1):
			for j in range(1, amt + 1):
				if nums[i - 1] <= j:
					dp[i][j] = min(1 + dp[i][j - nums[i - 1]], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[n][amt]

	def MinCoin(self, nums, amount):
		n = len(nums)
		val = self.help(nums, amount, n)
		if val == float('inf'):
			return -1
		else:
			return val


class Solution:

	def MinCoin(self, nums, amount):
		dp = [amount + 1] * (amount + 1)
		dp[0] = 0
		for each_amo in range(1, amount + 1):
			for coin in nums:
				if each_amo - coin >= 0:
					dp[each_amo] = min(dp[each_amo], 1 + dp[each_amo - coin])
		return dp[amount] if dp[amount] != amount + 1 else -1


class Solution:

	def MinCoin(self, nums, amount):
		t = [[0 for i in range(amount + 1)] for j in range(len(nums) + 1)]
		for i in range(1, len(nums) + 1):
			t[i][0] = 0
		for j in range(amount + 1):
			t[0][j] = amount + 2
		for k in range(1, amount + 1):
			if k % nums[0] == 0:
				t[1][k] = k // nums[0]
			else:
				t[1][k] = amount + 2
		for i in range(2, len(nums) + 1):
			for j in range(1, amount + 1):
				if nums[i - 1] <= j:
					t[i][j] = min(t[i][j - nums[i - 1]] + 1, t[i - 1][j])
				else:
					t[i][j] = t[i - 1][j]
		if t[len(nums)][amount] == amount + 2:
			return -1
		return t[len(nums)][amount]


class Solution:

	def MinCoin(self, nums, amount):
		dp = [[0] * (amount + 1) for _ in range(len(nums) + 1)]
		for j in range(1, amount + 1):
			dp[0][j] = 10 ** 9
		for i in range(1, len(nums) + 1):
			for j in range(1, amount + 1):
				if j >= nums[i - 1]:
					dp[i][j] = min(dp[i - 1][j], dp[i][j - nums[i - 1]] + 1)
				else:
					dp[i][j] = dp[i - 1][j]
		ans = dp[len(nums)][amount]
		if ans >= 10 ** 9:
			return -1
		return ans


class Solution:

	def MinCoin(self, nums, amount):
		dp = [0] * (amount + 1)
		nums.sort()
		for amt in range(1, amount + 1):
			ans = float('inf')
			for coin in nums:
				if coin <= amt:
					ans = min(ans, 1 + dp[amt - coin])
				else:
					break
			dp[amt] = ans
		if dp[amt] >= 10 ** 7:
			return -1
		else:
			return dp[amt]


class Solution:

	def MinCoin(self, nums, amount):
		memo = {}
		nums.sort(reverse=True)

		def helper(n, amt):
			if amt == 0:
				return 0
			if n == 0:
				return float('inf')
			elif (n, amt) in memo:
				return memo[n, amt]
			else:
				val = nums[n - 1]
				if val <= amt:
					c1 = 1 + helper(n, amt - val)
					c2 = helper(n - 1, amt)
					c = min(c1, c2)
				else:
					c = float('inf')
				memo[n, amt] = c
				return c
		res = helper(len(nums), amount)
		if res >= 10 ** 7:
			return -1
		else:
			return res


class Solution:

	def MinCoin(self, coins, Sum):
		N = len(coins)
		MAX = pow(10, 7)
		dp = [[MAX for j in range(Sum + 1)] for i in range(N)]
		for i in range(N):
			for s in range(Sum + 1):
				if i == 0 and s % coins[0] == 0:
					dp[0][s] = int(s / coins[0])
				else:
					notTake = dp[i - 1][s]
					take = MAX
					if coins[i] <= s:
						take = 1 + dp[i][s - coins[i]]
					dp[i][s] = min(take, notTake)
		return -1 if dp[N - 1][Sum] == MAX else dp[N - 1][Sum]


class Solution:

	def MinCoin(self, coins, Sum):
		N = len(nums)
		MAX = pow(10, 7)
		dp = [[-1 for j in range(Sum + 1)] for i in range(N)]

		def f(i, s):
			if i == 0:
				if s % coins[0] == 0:
					return int(s / coins[0])
				return MAX
			if dp[i][s] == -1:
				t = MAX
				nt = f(i - 1, s)
				if coins[i] <= s:
					t = 1 + f(i, s - coins[i])
				dp[i][s] = min(nt, t)
			return dp[i][s]
		ans = f(N - 1, Sum)
		return -1 if ans == MAX else ans


class Solution:

	def MinCoin(self, nums, amount):
		m = {}
		n = len(nums)
		nums.sort()

		def mincoin(i, s):
			if s == 0:
				return 0
			if i < 0:
				return 999999
			if s % nums[i] == 0:
				return s // nums[i]
			if (i, s) in m:
				return m[i, s]
			t = 999999
			h = 999999
			if nums[i] <= s:
				t = 1 + mincoin(i, s - nums[i])
			h = mincoin(i - 1, s)
			m[i, s] = min(t, h)
			return m[i, s]
		d = mincoin(n - 1, amount)
		if d == 999999:
			return -1
		return d


class Solution:

	def MinCoin(self, nums, amount):
		n = len(nums)
		dp = [[-1] * (amount + 1) for _ in range(n)]

		def rec(i, val):
			if i >= n:
				return 10001
			if val == 0:
				dp[i][val] = 0
				return 0
			if dp[i][val] != -1:
				return dp[i][val]
			coins = rec(i + 1, val)
			if nums[i] <= val:
				coins = min(1 + rec(i, val - nums[i]), coins)
			dp[i][val] = coins
			return dp[i][val]
		res = rec(0, amount)
		if res < 10001:
			return res
		else:
			return -1


def f(A, amt, dp):
	if amt == 0:
		return 0
	elif amt < 0:
		return int(100000.0)
	else:
		if dp[amt] != -1:
			return dp[amt]
		ans = int(100000.0)
		for i in A:
			ans = min(ans, 1 + f(A, amt - i, dp))
		if ans >= int(100000.0):
			ans = int(100000.0)
		dp[amt] = ans
		return ans

class Solution:

	def MinCoin(self, nums, amount):
		dp = [-1] * (amount + 1)
		ans = f(nums, amount, dp)
		if ans == int(100000.0):
			return -1
		return ans


class Solution:

	def MinCoin(self, n, a):
		dp = [0] * (a + 1)
		for i in range(1, a + 1):
			dp[i] = 100000000
			for j in range(len(n)):
				if i - n[j] >= 0:
					su = dp[i - n[j]]
					dp[i] = min(dp[i], su + 1)
		if dp[a] == 0 or dp[a] == 100000000:
			return -1
		else:
			return dp[a]


class Solution:

	def MinCoin(self, nums, amount):
		dp = [amount + 1] * (amount + 1)
		dp[0] = 0
		for a in range(1, amount + 1):
			for c in nums:
				if a - c >= 0:
					dp[a] = min((dp[a], 1 + dp[a - c]))
		return dp[amount] if dp[amount] != amount + 1 else -1


import sys

class Solution:

	def MinCoin(self, nums, amount):
		prev = [0] * (amount + 1)
		for i in range(amount + 1):
			if i % nums[0] == 0:
				prev[i] = i // nums[0]
			else:
				prev[i] = sys.maxsize
		for index in range(1, len(nums)):
			cur = []
			for target in range(amount + 1):
				(notTake, take) = (prev[target], sys.maxsize)
				if nums[index] <= target:
					take = 1 + cur[target - nums[index]]
				cur.append(min(notTake, take))
			prev = cur
		t = prev[-1]
		if t == sys.maxsize:
			return -1
		return t


import sys

class Solution:

	def MinCoin(self, nums, amount):
		ans = [[0] * (amount + 1) for _ in range(len(nums))]
		for i in range(amount + 1):
			if i % nums[0] == 0:
				ans[0][i] = i // nums[0]
			else:
				ans[0][i] = sys.maxsize
		for index in range(1, len(nums)):
			for target in range(amount + 1):
				(notTake, take) = (ans[index - 1][target], sys.maxsize)
				if nums[index] <= target:
					take = 1 + ans[index][target - nums[index]]
				ans[index][target] = min(notTake, take)
		t = ans[-1][-1]
		if t == sys.maxsize:
			return -1
		return t


import sys

class Solution:

	def MinCoin(self, nums, amount):
		ans = [[-1] * (amount + 1) for _ in range(len(nums) + 1)]

		def selectCoin(index, T):
			if index == 0:
				if T % nums[0] == 0:
					return T // nums[0]
				return sys.maxsize
			if ans[index][T] != -1:
				return ans[index][T]
			notTake = selectCoin(index - 1, T)
			take = sys.maxsize
			if nums[index] <= T:
				take = 1 + selectCoin(index, T - nums[index])
			ans[index][T] = min(notTake, take)
			return ans[index][T]
		t = selectCoin(len(nums) - 1, amount)
		if t == sys.maxsize:
			return -1
		return t


class Solution:

	def MinCoin(self, coins, N):
		dp = [N + 1] * (N + 1)
		dp[0] = 0
		for i in range(1, N + 1):
			for j in coins:
				if i - j >= 0:
					dp[i] = min(dp[i], 1 + dp[i - j])
		return dp[N] if dp[N] != N + 1 else -1


INV = 10 ** 9

class Solution:

	def MinCoin(self, A, K):
		dp = [INV] * (K + 1)
		dp[0] = 0
		for amt in range(1, K + 1):
			for v in A:
				if v > amt:
					continue
				dp[amt] = min(1 + dp[amt - v], dp[amt])
		return dp[K] if dp[K] < INV else -1


class Solution:

	def MinCoin(self, nums, amount):
		n = len(nums)
		dp = [[0] * (amount + 1) for tt in range(n + 1)]
		dp[0] = [0] + [amount + 1] * amount
		for i in range(1, amount + 1):
			for j in range(1, n + 1):
				if nums[j - 1] <= i:
					dp[j][i] = min(1 + dp[j][i - nums[j - 1]], dp[j - 1][i])
				else:
					dp[j][i] = dp[j - 1][i]
		if dp[-1][-1] < amount + 1:
			return dp[-1][-1]
		return -1


class Solution:

	def MinCoin(self, coins, sum):
		dp = [[0] * (sum + 1) for i in range(len(coins) + 1)]
		for i in range(1, sum + 1):
			dp[0][i] = 10 ** 5
		for i in range(1, len(coins) + 1):
			for j in range(sum + 1):
				if j >= coins[i - 1]:
					dp[i][j] = min(dp[i - 1][j], 1 + dp[i][j - coins[i - 1]])
				else:
					dp[i][j] = dp[i - 1][j]
		if dp[-1][-1] > 10 ** 4:
			return -1
		else:
			return dp[-1][-1]


def cc(arr, n, dp):
	if n == 0:
		return 0
	if dp.get(n):
		return dp[n]
	ans = float('inf')
	for i in range(len(arr)):
		if n - arr[i] >= 0:
			sub = 0
			if dp.get(n - arr[i]):
				sub = dp[n - arr[i]]
			else:
				sub = cc(arr, n - arr[i], dp)
			if sub != float('inf') and sub + 1 < ans:
				ans = sub + 1
	dp[n] = ans
	return dp[n]

class Solution:

	def MinCoin(self, nums, amount):
		return cc(nums, amount, {0: 0}) if cc(nums, amount, {0: 0}) != float('inf') else -1


import sys

class Solution:

	def solve(self, nums, amount):
		dp = [float('inf')] * (amount + 1)
		dp[0] = 0
		mini = float('inf')
		for i in range(1, amount + 1):
			for j in range(len(nums)):
				if i - nums[j] >= 0 and dp[i - nums[j]] != float('inf'):
					dp[i] = min(dp[i], 1 + dp[i - nums[j]])
		if dp[amount] == float('inf'):
			return -1
		return dp[amount]

	def MinCoin(self, nums, amount):
		return self.solve(nums, amount)


from math import inf

class Solution:

	def MinCoin(self, x, amount):
		x = list(set(x))
		n = len(x)

		def f(i, s):
			if s == 0:
				return 0
			if i == n:
				return inf
			if dp[s][i] != -1:
				return dp[s][i]
			ans = inf
			t = 0
			while s - t * x[i] >= 0:
				ans = min(ans, t + f(i + 1, s - t * x[i]))
				t += 1
			dp[s][i] = ans
			return ans
		dp = [[-1 for i in range(n)] for j in range(amount + 1)]
		x.sort(reverse=True)
		a = f(0, amount)
		return a if a != inf else -1


class Solution:

	def MinCoin(self, arr, amount):
		N = len(arr)
		dp = [[0] * (amount + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for j in range(amount + 1):
				amt = j
				n = i
				if amt == 0:
					dp[i][j] = 0
				elif n == 0:
					dp[i][j] = float('INF')
				else:
					val = arr[n - 1]
					if val <= amt:
						c1 = 1 + dp[n][amt - val]
						c2 = dp[n - 1][amt]
						dp[i][j] = min(c1, c2)
					else:
						dp[i][j] = dp[n - 1][amt]
		val = dp[N][amount]
		if val >= 10 ** 9 + 7:
			return -1
		else:
			return val


class Solution:

	def MinCoin(self, arr, amount):
		dp = {}
		N = len(arr)
		arr.sort(reverse=True)

		def dynamic(N, amount):
			if N == 0:
				return float('INF')
			elif amount == 0:
				return 0
			elif (N, amount) in dp:
				return dp[N, amount]
			else:
				item = arr[N - 1]
				if item <= amount:
					c1 = 1 + dynamic(N, amount - item)
					c2 = dynamic(N - 1, amount)
					c = min(c1, c2)
				else:
					c = float('INF')
				dp[N, amount] = c
				return c
		item = dynamic(N, amount)
		if item > 10 ** 9 + 7:
			return -1
		else:
			return item