Using dedup
def dfs(coins, start, remaining, path):
n = len(coins)
if remaining == 0:
res.append(path[:])
return
for i in range(start, n):
coin = coins[i]
if remaining - coin < 0:
continue
dfs(coins, i, remaining - coin, path + [coin])
res = []
dfs(coins, 0, amount, [])
return len(sorted(res, key=len)[0]) if res else -1
Assuming we can sort the coins:
def coin_change(coins: List[int], amount: int) -> int:
result = 0
for coin in reversed(sorted(coins)):
result += amount // coin
amount = amount % coin
return result if amount == 0 else -1
this is greedy algorithm and does not work for all the cases
This code is not working for this input
1 2147483647
2
Can someone help.
I’m doing memoization with a dictionary like this:
def coin_change(coins: List[int], amount: int) → int:
memo = {}
def min_coins(coins, amount, sum):
if sum == amount:
return 0
if sum > amount:
return inf
if sum in memo:
return memo[sum]
ans = inf
for coin in coins:
res = min_coins(coins, amount, sum+coin)
if res == inf:
continue
ans = min(res+1, inf)
memo[sum]=ans
return ans
result = min_coins(coins, amount, 0)
return -1 if result == inf else result
but it’s not producing correct result for last case. any idea why?
Thanks in advance.
a far superior way of solving
const coinChange = (coins, amount) => {
const cl = coins.length;//length of the coins array
coins.sort((a, b) => b - a);
let count = 0;
const resMap = new Map(); //For Memoization
//sum: Sum made till date,index:index of symbol array ,l:level
const dfs = (sum, index, l) => {
count += 1;
if (sum === amount)
return 0;
else if (resMap.has(sum))
return resMap.get(sum);
let ans = -1;
for (let i = index; i < cl; i += 1) {
if (sum + coins[i] <= amount) {
const tans = dfs(sum + coins[i], i, l + 1);
if (tans !== -1 && ans !== -1)
ans = Math.min(ans, tans);
else if (tans !== -1 && ans === -1)
ans = tans;
}
}
if (l === 0)
console.log(count);
if (ans !== -1) {
resMap.set(sum, ans + 1);
return ans + 1;
}
resMap.set(sum, ans);
return ans;
}
return dfs(0, 0, 0);
}
you can check it by difference in count (how many number of times dfs function calls) value
problem
186 419 83 408
6249
Count = 17501 (For given solution) Count = 5814 (for my solution)
It’s wrong approach guys
sorry
ans = min(res+1, inf) should be ans = min(res+1, ans) cuz you want to compare with the existingans
Dear Moderator(s),
I approached this problem slightly differently. Instead of using sum, I pass remaining balance as a function argument (amount-coin). Initially, my balance is the amount itself. My DFS returns the minimum number of coins, which is also passed to it as a function argument. In each subsequent recursive call, I increment the min coins by 1. The base case is when the balance is zero, and I return the min coins function argument itself as my answer, because there are no more coins to add.
The code works for all test cases and as expected, times out for larger inputs. My question is what do I memo on? I intuitively used memo on the balance, but it doesn’t seem to work for all test cases. It only works for scenarios where the amount equals one of the coins in the list of coins. Why is this happening? Can you explain, what can I memo, in this approach?
Is this question same as the one in DP section?
Yes, it’s the same. you can solve it with bottom up dp too.
I approached the same way and found a memo approach that works
def coin_change(coins: List[int], amount: int) → int:
memo = {}
def impl(num_coins: int, amt_left: int) -> int:
if amt_left in memo:
return memo[amt_left] + num_coins
if amt_left == 0:
return num_coins
run_min = inf
for coin in coins:
if amt_left - coin < 0:
continue
tmp_num_coins = impl(num_coins + 1, amt_left - coin)
run_min = min(tmp_num_coins, run_min)
memo[amt_left] = run_min - num_coins
return run_min
ans = impl(0, amount)
if ans == inf:
return -1
else:
return ans
How would we find the list of coins used along with the minimum number of coins with this logic?
Memoization template Solution with a little bit of brevity
def coin_change(coins: List[int], amount: int) → int:
memo = [-1] * amount
def dfs(current_sum):
if current_sum == amount:
return 0
if current_sum > amount:
return inf
if memo[current_sum] != -1:
return memo[current_sum]
min_coin = inf
for coin in coins:
result = dfs(current_sum + coin)
if result != inf:
min_coin = min(min_coin, result + 1)
memo[current_sum] = min_coin
return min_coin
result = dfs(0)
return result if result != inf else -1
Tracking the difference instead of sum
Key note:
Memorization of amount instead of sum
private static int dfs(List<Integer> coins, int amount, int[] memo) {
if (amount == 0) {
return 0;
}
if (memo[amount] != -1) {
return memo[amount];
}
int min = Integer.MAX_VALUE;
for (int c : coins) {
if (amount - c >= 0) { // This guard can be factored out
int res = dfs(coins, amount - c, memo);
if (res == Integer.MAX_VALUE) {
continue;
}
min = Math.min(min,res + 1);
}
}
memo[amount] = min;
return min;
}
My solution is more similar to our template in aggregation.
def coin_change(coins: List[int], amount: int) -> int:
# WRITE YOUR BRILLIANT CODE HERE
def dfs(left, steps):
if left == 0:
return steps
ans = float("Inf")
for c in coins:
if left < 0:
continue
res = dfs(left-c, steps+1)
ans = min(ans, res)
return ans
out = dfs(amount, 0)
if out == float("Inf"):
return -1
return out
Agree to people above, leftover amount approach is easier to understand and implement and it also better correlates with what we learned before
The solution still works, however we need to initiate an Integer array instead of int array.
Why?
coz Integer array is null by default,
Using DP’s concept to do dfs
def coin_change(coins: List[int], amount: int) -> int:
def dfs(remained_amount, mem={}):
if remained_amount in mem:
return mem[remained_amount]
if remained_amount == 0:
return 0
if remained_amount < 0:
return float("inf")
min_nums = float("inf")
for coin in coins:
min_nums = min(min_nums, dfs(remained_amount - coin) + 1)
mem[remained_amount] = min_nums
return min_nums
min_nums = dfs(amount)
return -1 if min_nums == float("inf") else min_nums