Minimum Coin Change Problem in Dynamic Programming is the most asked frequent questions asked in Software Coding Interview. Today we will be looking at the solution of this problem.

## Coin Change – LeetCode

You are given an integer array of coins representing coins of different denominations and an integer amount representing a total amount of money.

Return *the fewest number of coins that you need to make up that amount*. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

**Example 1:**

Input:coins = [1,3,5], amount = 11Output:3Explanation:11 = 5 + 5 + 1

**Example 2:**

Input:coins = [1], amount = 3Output:-1

## Solution in Python

from collections import deque class Solution: def coinChange(self, coins: List[int], amount: int) -> int: qset = set() qeu = deque() qset.add(amount) qeu.append((0, amount)) # (num coins, amount) while q: (num_coins, rem) = qeu.popleft() if rem == 0: return num_coins if rem < 0: continue for coin in coins: x = rem - coin if x not in qset: qeu.append((num_coins + 1, x)) qset.add(x) return -1

## Solution in C++

class Solution { public: int coinChange(vector<int>& coins, int amount) { int getCoinCount = coins.size(); //cache to store minimum number of coins needed for each sub amount less than the target vector<int> cache(amount + 1, INT_MAX); //If amount is 0, no coin is needed cache[0] = 0; //Calculate the minimum number of coins needed for each amount less than target amount. //Use the minimum cains needed for lower amounts in calculating coins needed for higher amount. for (int currAmount = 1; currAmount <= amount; currAmount++) { for (int coinIdx = 0; coinIdx < getCoinCount; coinIdx++) { if (coins[coinIdx] <= currAmount) { int sub_result = cache[currAmount - coins[coinIdx]]; if (sub_result != INT_MAX && sub_result + 1 < cache[currAmount]) cache[currAmount] = sub_result + 1; } } } return cache[amount] != INT_MAX ? cache[amount] : -1; } };

If you liked the answer then please follow us on **Facebook **and **Twitter**. Let us know the questions and answer you want to cover in this blog.

Wanna read more interview related questions ? **Check Top Interview Questions category**.