Coin Change - Dynamic Programming Bottom Up - Leetcode 322

0:00 - Read the problem
1:30 - Greedy doesn't work
3:05 - DFS Solution
10:40 - Dynamic Programming
15:35 - Coding Solution

leetcode 322

#leetcode #programming #python

Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[MP-nyep]

Love how you went from the greedy approach to the brute force dfs approach to the optimal dp approach. It helped me understand this problem better. Thank you !

[perelium-x]

For those having a hard time with dp just some advice
1. Decision Trees
2. Recursion
3. Optimal Substructure and Overlapping Subproblem

then just Memoize
you have urself dp

tc

[adithyagowda]

The way you explained DFS approach and converted it into a DP solution was just freaking amazing!!! It's exactly what I was looking for. I now feel confident in converting my DFS solutions into DP solution. Thank you very much!

[CodeWMatt]

I had this problem on a test in my first programming class in college. Not a single person in my section got it correct and the professor did not go over how to solve it. That test was a 2 years ago, and I have not fully understood the solution until just now. This is a weird feeling. Thank you NeetCode.

[richard]

actually neet's explanation to compare dfs, greedy and then using dp is soo rad and lowkey!! man u are awesome. give me a few more days i am gonna start donating for ur coffee's each week

[satyajeetkumarjha]

Your dp code is similar to what most of us will code but your code is more readable. Highly appreciable .

[souravchakraborty]

Anyone curious about top to bottom recursion(backtracking with memoization) :
def coinChange(self, coins: List[int], amount: int):
memo = {}
def dfs(amount):


if amount == 0:
return 0
if amount<0:
return float('inf')
if amount in memo:
return memo[amount]

memo[amount] = min([1+dfs(amount-c) for c in coins])
return memo[amount]


minimum = dfs(amount)
return minimum if minimum < float("inf") else -1

[cody_code]

Wow, I was so stumped on this concept until I found this video. Thanks for going the extra mile with the explanation!

[DoJoStan]

Excellent explanation, I was trying to wrap my head around the bottom up approach solution described on leetcode and you illustrated it perfectly.

[dheepthaaanand]

For case like coins 2 4 5, amount 3, where you can't sum up, if we try with 2, we'll get min(4, 1+dp[1]) and dp[1] would be equal to default 4 because all coin values were greater (a-c < 0), so we get 1+4=5, and min of both is 4. So in short, for these cases where amount is greater than some coin values but you can't sum up, you'll get 1+dp[difference] as greater than amount+1, so amount+1 will always be min, and allow us to return -1 at the end

[wilsonwang]

The part at 12:20 really helps me to clarify the problem. Thanks bro Neetcode, you produce really meaningful content.

[yipeng]

You are more qualified than most university instructors on introducing DSA topics, no joke

[halahmilksheikh]

For anyone curious, here's what the top down DP with memoization looks like. It's very slow. If you remove the memoization, you get a time limit exceeded but it still "works"

var coinChange = function(coins, amount) {
let memo = [] // with memoization
let ret = dfs(amount)

if (ret == Infinity) ret = -1
return ret

function dfs(target) { // returns min from all paths
if (target < 0) {
return Infinity
}

if (target == 0) {
return 0
}

if (memo[target] != null) {
return memo[target]
}
memo[target] = Infinity

for (let coin of coins) {
memo[target] = Math.min(memo[target], 1 + dfs(target - coin))
}
return memo[target]
}
};

[pomegranate]

excellent, I love how patient and carefully u explain instead of rushing stuff and skipping steps <3

[inquisitorshampoo]

Have my amazon interview in 10 minutes. Your videos have been incredibly helpful while studying!

[linli]

When I search for a solution for a problem on leetcode, I will watch your video first. Excellent explanation!

[rachelwilliams]

For the range you are looping over in line 6, you don't need to go from 1..amount + 1. You only need to loop from 1 to the amount since you already covered 0 before the loop.

[madixit]

Impressed, I was going nuts with leet code premium explanation. I owe you👌

[wlcheng]

Brilliant explanation! I was able to come up with the code by myself after understanding your solution. And the implementation is quite similar to yours. Guess I followed your coding style pretty well. 😆

[ahmadbasyouni]

your channel saves me so much time than trying to read the weird wording of the editorial on LC appreciate you man!