Dare2Solve
The coin change problem is a classic dynamic programming problem where you are given a set of coin denominations and a target amount. The goal is to find the minimum number of coins needed to make up that amount. If it is not possible to make up the amount with the given coins, return -1.
The intuition behind solving the coin change problem is to use a recursive approach with memoization to minimize redundant calculations. The problem can be broken down into subproblems where we try to make change for smaller amounts and build up the solution for the target amount. By storing the results of these subproblems, we can efficiently find the minimum number of coins needed.
Base Cases:
Recursive Function:
dfs(remaining)
that returns the minimum number of coins needed for the given remaining
amount.remaining
is already computed (exists in the memoization map dp
), return the stored result to avoid redundant calculations.remaining - coin
.Memoization:
Final Result:
O(amount * n), where amount
is the target amount and n
is the number of different coin denominations. This is because in the worst case, we need to compute the result for each amount from 1 to the target amount, and for each amount, we check all coin denominations.
O(amount), which is the space required for the memoization map (or array) to store the minimum number of coins needed for each amount from 0 to the target amount.
class Solution {
public:
int coinChange(std::vector<int>& coins, int amount) {
if (amount == 0) return 0;
std::unordered_map<int, int> dp;
int result = dfs(coins, amount, dp);
return result == INT_MAX ? -1 : result;
}
private:
int dfs(std::vector<int>& coins, int remaining, std::unordered_map<int, int>& dp) {
if (remaining < 0) return INT_MAX;
if (remaining == 0) return 0;
if (dp.find(remaining) != dp.end()) return dp[remaining];
int minCoins = INT_MAX;
for (int coin : coins) {
int res = dfs(coins, remaining - coin, dp);
if (res != INT_MAX) {
minCoins = std::min(minCoins, 1 + res);
}
}
dp[remaining] = minCoins;
return minCoins;
}
};
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if amount == 0:
return 0
dp = {}
def dfs(remaining):
if remaining < 0:
return float('inf')
if remaining == 0:
return 0
if remaining in dp:
return dp[remaining]
min_coins = float('inf')
for coin in coins:
res = dfs(remaining - coin)
if res != float('inf'):
min_coins = min(min_coins, 1 + res)
dp[remaining] = min_coins
return dp[remaining]
result = dfs(amount)
return -1 if result == float('inf') else result
class Solution {
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
Map<Integer, Integer> dp = new HashMap<>();
int result = dfs(coins, amount, dp);
return result == Integer.MAX_VALUE ? -1 : result;
}
private int dfs(int[] coins, int remaining, Map<Integer, Integer> dp) {
if (remaining < 0) return Integer.MAX_VALUE;
if (remaining == 0) return 0;
if (dp.containsKey(remaining)) return dp.get(remaining);
int minCoins = Integer.MAX_VALUE;
for (int coin : coins) {
int res = dfs(coins, remaining - coin, dp);
if (res != Integer.MAX_VALUE) {
minCoins = Math.min(minCoins, 1 + res);
}
}
dp.put(remaining, minCoins);
return minCoins;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] coins = {1, 2, 5};
int amount = 11;
System.out.println(solution.coinChange(coins, amount)); // Output: 3
}
}
var coinChange = function(coins, amount) {
if(amount === 0) return 0
dp = {}
function dfs(total){
if(total > amount){
return Infinity
}
if(total === amount) return 0;
if(dp[total]){
return dp[total]
}
let temp = Infinity
for(let i =0; i<coins.length; i++){
temp = Math.min(temp, 1+dfs(total+coins[i]))
}
dp[total] = temp
return dp[total]
}
result = dfs(0)
return result === Infinity ? -1 : result
};