We can also initialize the array with amount instead of amount + 1 right, because the maximum number of coins used will be in the case where each coin you use is a 1 coin?
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 !
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
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!
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
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
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] } };
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. 😆
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.
I watched this problem in so many videos but all of them was forcing me to remember things and making this problem complex but you made it so intuitive like it's damm easy, thanks for helping :)
There’s also a simple recursive way of doing this problem. Take the amount of change you’re looking for, find the largest denomination that does not go over the amount of change being requested, subtract that denomination from the amount requested, and call the same function with the new value. To account for values that are higher than the largest denomination, simply take the change amount value and subtract the integer division value that results from the change requested divided by the largest denomination, and again, call the function recursively.
Good explantion starting from recursion tree. However, during the transformation from recursion to bottom up dp, I really tried to search the answer to my 2 confusion, yet failed to find it. 1. How did dp resolve the problem of dupliactes, eg, 1,5,1 and 1,1,5 are essentially the same and if we do through recursion, we have to add logic ro avoid that, but why dp arrays don't have to? 2. How does it evolevs into a knapsack (take or not take ) problem? In another word, why dp[a]=min(dp[a], dp[a-c])? Looking forward to your reply to rsolve my huge confusions. Thanks!
Duplicates don't matter here because what is cached is the minimum coins used. With your example, DP[7] is 3 whichever coin options are used. If the question has asked, return all the possible combinations of coins that make up the minimum number of coins uses, and the question explicitly asks you to dedupe cases like 1,1,5 and 1,5,1, then you have to care about dupes.
@@sumitevs I think we can think of it in a different way. dp[a] = 1+min(dp[a-c1],dp[a-c2], ...dp[a-ci]) where 1 to i is the different denominations of coins given. It looks confusing in code because he is doing a loop over ci and storing the min in dp[a] itself after every iteration.
i commented on the code for my learning hopefully this is helpful class Solution(object): def coinChange(self, coins, amount): """ :type coins: List[int] :type amount: int :rtype: int """ dp = [amount + 1] * (amount + 1) # 0 to amount so amount + 1 in total dp[0] = 0 # base case, amount 0 takes 0 coins print(dp) #bottom up order for a in range(1, amount + 1): # to get to each number in 1 to the amount + 1 for c in coins: # go through every coin if a - c >= 0: # remainder dp[a] = min(dp[a], 1 + dp[a - c]) # go through every possible solution # coin = 4, a = 7, dp[7] = 1 + dp[7-4] = 1 + dp[3] # dp stores the number of coins needed to get to that number, therefore we get 1 for in 1 + dp[a - c] for an additional coin needed
print(dp) return dp[amount] if dp[amount] != amount + 1 else -1 # dp[amount] != amount + 1 is the default value
I know this problem is best solved by using Dynamic Programming, but I want to focus on the Brute Force solution: I can say it is Divide and Conquer: We are dividing the problem into smaller sub-problems, solving individually and using those individual results to construct the result for the original problem. I can also say it is Backtracking: we are enumerating all combinations of coin frequencies which satisfy the constraints. I know both are implemented via Recursion, but I would like to know which paradigm the Brute Force solution belongs to: Divide and Conquer or Backtracking.
Great video, great explanation. It starts from the brute force approach to build up he required intuition to eventually realize we can use a DP based solution. Thank you very much. One thing I wish to comment is that I am now curious to see a DP top-down recursive solution based on memoization. ;)
Here is the python DP top-down recursive solution with memoization. It took me some time to come up with it. class Solution: def __init__(self): self.memo = {} self.coins = None
minc = float("inf") for c in self.coins: if amount < c: break res = self.coinChange(coins=None, amount=amount-c) if res == -1: continue minc = min(res + 1, minc)
res = -1 if minc == float('inf') else minc self.memo[amount] = res return res
I don't think this solution would work in all cases. Let's say you can only use the coins (2, 5, 10) to return a value of 2, at the first iteration and when trying to calculate dp[1] you're gonna find out that no coin is smaller that 1 so the condition "a - c >= 0" will not be met, and so dp[1] will stay equal to amount+1 (and this is gonna screw what comes next). So if you try to know the number of coins needed to return a value of 2 (it should be 1 cause we have 2 in our list of coins), this algorithm will return -1 because you will have dp[2] = amount+1. I'm not sure if i explained my process of thoughts right, if you think i'm wrong i'd be happy to learn.
Nice and short functional programming style solution: dp = [0] for i in range(1, amount+1): options = [dp[i-x] for x in coins if i >= x and dp[i-x] != -1] dp.append(-1 if not options else 1+min(options)) return dp[amount]
Greedy does work if we remove the biggest coin at every full iteration and keep checking for the minimum amount of change. This, however, is pretty inefficient.
i'm from Brazil. And you gained more one subscriber.Because your explanation is very good and you talk so cleary that i can undestand you. And this is so good for me that i'm learning english.
BFS with a Bitmap is also accepted, with the same complexity. Almost the same memory footprint but DP is a lot faster. Sequential memory access is very efficient.
If you are struggling to understand why we updated dp[i] when (i - coins[j] >= 0) the key insight is that dp[i] only gets updated if there is a solution that leads to zero (even when this condition evaluates to true). That is, there are cases where (i - coins[j] >= 0) but dp[i] remains "amount + 1". For instance if we have amount = 11 and coins = [2, 4, 6], when we get to i = 3, we find that 3 - 2 >= 0. However, min(dp[3], 1 + dp[3 - 2]) causes dp[3] to remain "amount + 1" as there is no valid solution leading to zero that we captured at dp[1] (that is, dp[1] itself still equals "amount + 1").
Good. You can start at min coin value in the outer for loo. It takes O(len(coins)) extra time to find the min. Helps in cases where amount is too large and number of coins of small.
First understand DFS very well, and then try to understand bottom-up DP concept. Coding is trivial, but understanding the whole solution is really hard.
Sick, I tried this for the first time on my own and used BFS to find the "shortest path". Sadly I knew I needed to optimize it with caching but couldn't figure out the right way to implement it. When I saw I only needed 3 extra lines to finish my solution I felt hella dumb. But this is a really good problem.
couple questions: 1. dp[a] = min(dp[a], 1 + dp[a - c]), why should compare itself with 1 + dp[a-c]? is it possible dp[a] it self less than 1 + dp[a- c]? 2. why the condition is if dp[amount] != amount + 1:? if coins = [2], amount = 3, how should it explain under this situation? I am so confused.
The correct solution on leetcode has ur OUTER loop as its INNER LOOP and your INNER loop as its OUTER loop. Why is it switched around? For example the solution on leetcode says this: Bottom up DP class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp=[math.inf] * (amount+1) dp[0]=0 for coin in coins: for i in range(coin, amount+1): if i-coin>=0: dp[i]=min(dp[i], dp[i-coin]+1) return -1 if dp[-1]==math.inf else dp[-1]
self notes: Not greedy - since 5 + 1 + 1 will not work; backtracking - yea but overlapping subproblems so can use DP; Memoization works ; now think in reverse and do bottoms up .
One more thing, if you initialize dp[0] = 1 then you don't need to do 1+ dp[a-c] and this is okay because what is the no of ways to make sum 0 out of n no of coins , the answer is 1 i.e don't consider any coin
15:53 This is false! If you set each value to infinity, it will lead to an overflow when you do the Math.Min(dp[i], dp[i - coins[j]] + 1); That + 1 will cause it to overflow to a large -ve number and that will throw your answer off by a large margin. Otherwise, you're right it could be any large value BUT with the constraints of the question, the only safe value we can put it amount + 1 since the min denomination of a coin is 1 and that would cause our total number of coins to be at max amount only.
Does time complexity differ if we choose top-down dynamic programming? I think top-down is better because we don't have to compute every number in the range of amount. Am I right?
Was this the very first solution that came to your mind? When I'm seeing these types of solutions, I wonder if there's like ideas eliminated before coming to such a structured solution like this one. I'm posing the question because I wonder if this would be like the first solution you'd think of during a timed technical interview
you can not come up with such a structured solution in an interview setting unless you have done SIMILAR problem before. call it a curse or a blessing , it is what it is. p.s. i hate it.
Hi NeetCode. You say that for this problem, you cannot choose a greedy method to solve it. What's an example of a case where you *could* be greedy? Thank you :)
Very well explained. I'm a newbie to dp in general, Do people solve these problems off head in interviews? or they just cram the solutions and go for it, because I'm having trouble wrapping my head around these problems.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
We can also initialize the array with amount instead of amount + 1 right, because the maximum number of coins used will be in the case where each coin you use is a 1 coin?
@@aaditkamat4995 what if you have to form amount 10 and you have only 1 unit coin , than total number of coins will be 10 which is equal to the amount
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 !
Dynamic Programming is so confusing!!!!!!
yes its hard for me at begining, you should try with cases that has shaloe level of recursive and learn from there
YET beautiful :D
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
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!
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
Thanks appreciate it a lot 😊
@richard12345789 Have you started donating. 😂?
Your dp code is similar to what most of us will code but your code is more readable. Highly appreciable .
Wow, I was so stumped on this concept until I found this video. Thanks for going the extra mile with the explanation!
The part at 12:20 really helps me to clarify the problem. Thanks bro Neetcode, you produce really meaningful content.
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
thanks i was actually searching for this
excellent, I love how patient and carefully u explain instead of rushing stuff and skipping steps
Excellent explanation, I was trying to wrap my head around the bottom up approach solution described on leetcode and you illustrated it perfectly.
same! I was lost at what dp[i - coin[j]] meant, and it finally clicked when I watched this video at the @13:30s mark. Ty!
love your videos mate
whenever I am stuck I go straight to your channel instead of 'Solution' section.
Keep it coming!
Have my amazon interview in 10 minutes. Your videos have been incredibly helpful while studying!
How was your interview ?
@@chuongtruong7090 good! ended up getting an offer
@@inquisitorshampoo1043 Wow, congrats !!!!
@@inquisitorshampoo1043 goddamn so lucky. I got rejected by google, a week ago. I cry.
@@EDROCKSWOO what questions did they ask you?
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]
}
};
why is it slow? I wrote it in python and it was just as fast as the dp solution he gave us...
@@mastermax7777 Agreed, shouldn't it be the same complexity?
It only checks the number of paths to `0` once for each `range(amount)`.
When I search for a solution for a problem on leetcode, I will watch your video first. Excellent explanation!
I was so close here but this helped to sort it out for me. Hands down the best explanations on this stuff. Thank you so much for this!
You are more qualified than most university instructors on introducing DSA topics, no joke
Awesome explanation! I was stuck with the top down approach and how to convert it to the DP solution, and this made it all click.
Thanks!
your channel saves me so much time than trying to read the weird wording of the editorial on LC appreciate you man!
Impressed, I was going nuts with leet code premium explanation. I owe you👌
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. 😆
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.
I watched this problem in so many videos but all of them was forcing me to remember things and making this problem complex but you made it so intuitive like it's damm easy, thanks for helping :)
You had made the best explanation found on youtube for this problem, with 3 different approaches. Thanks, buddy.
Dynamic Programming is always so fuzzy to me. Thank you for explaining!
There’s also a simple recursive way of doing this problem.
Take the amount of change you’re looking for, find the largest denomination that does not go over the amount of change being requested, subtract that denomination from the amount requested, and call the same function with the new value.
To account for values that are higher than the largest denomination, simply take the change amount value and subtract the integer division value that results from the change requested divided by the largest denomination, and again, call the function recursively.
This is such a hard question and I am really thankful that you are here to help to explain how to proceed with dp problems...
Thanks for the help... I figured out top-down memoization on my own, so fortunately most of my work carried over to the bottom-up approach.
Thank you so much for the thought process of how to get to the dynamic programming solution!
I got this question in an Amazon technical interview. I wish I saw this video beforehand
Good explantion starting from recursion tree. However, during the transformation from recursion to bottom up dp, I really tried to search the answer to my 2 confusion, yet failed to find it.
1. How did dp resolve the problem of dupliactes, eg, 1,5,1 and 1,1,5 are essentially the same and if we do through recursion, we have to add logic ro avoid that, but why dp arrays don't have to?
2. How does it evolevs into a knapsack (take or not take ) problem? In another word, why dp[a]=min(dp[a], dp[a-c])?
Looking forward to your reply to rsolve my huge confusions. Thanks!
i have the same doubt. why dp[a]=min(dp[a], dp[a-c])?
Duplicates don't matter here because what is cached is the minimum coins used. With your example, DP[7] is 3 whichever coin options are used.
If the question has asked, return all the possible combinations of coins that make up the minimum number of coins uses, and the question explicitly asks you to dedupe cases like 1,1,5 and 1,5,1, then you have to care about dupes.
@@sumitevs I think we can think of it in a different way. dp[a] = 1+min(dp[a-c1],dp[a-c2], ...dp[a-ci]) where 1 to i is the different denominations of coins given. It looks confusing in code because he is doing a loop over ci and storing the min in dp[a] itself after every iteration.
thank you, man, couldn't solve on my own and didn't understand both the Editorial and one of the top submissions. Only your explanation did it for me!
Best Explanation on Dynamic Programming in a Scientific Approach!! 🙌🏻
Really good explanation of the 1+dp[a] and what the 1 means in this case- because we’re using one coin as we’re iterating through the coins
Your explanations skills are really amazing! Definitely very helpful! 🤓
Thank you! Definitely better explanation than the leetcode's explanation!
Glad it was helpful!
Bro, your explanations are so good. Keep up the amazing work!
i commented on the code for my learning hopefully this is helpful
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
dp = [amount + 1] * (amount + 1) # 0 to amount so amount + 1 in total
dp[0] = 0 # base case, amount 0 takes 0 coins
print(dp)
#bottom up order
for a in range(1, amount + 1): # to get to each number in 1 to the amount + 1
for c in coins: # go through every coin
if a - c >= 0: # remainder
dp[a] = min(dp[a], 1 + dp[a - c]) # go through every possible solution
# coin = 4, a = 7, dp[7] = 1 + dp[7-4] = 1 + dp[3]
# dp stores the number of coins needed to get to that number, therefore we get 1 for in 1 + dp[a - c] for an additional coin needed
print(dp)
return dp[amount] if dp[amount] != amount + 1 else -1
# dp[amount] != amount + 1 is the default value
for those who wanna know the optimal, check bidirectional BFS with DP, it beats 99.6%
? how?
I know this problem is best solved by using Dynamic Programming, but I want to focus on the Brute Force solution:
I can say it is Divide and Conquer: We are dividing the problem into smaller sub-problems, solving individually and using those individual results to construct the result for the original problem.
I can also say it is Backtracking: we are enumerating all combinations of coin frequencies which satisfy the constraints.
I know both are implemented via Recursion, but I would like to know which paradigm the Brute Force solution belongs to: Divide and Conquer or Backtracking.
Great video, great explanation. It starts from the brute force approach to build up he required intuition to eventually realize we can use a DP based solution. Thank you very much.
One thing I wish to comment is that I am now curious to see a DP top-down recursive solution based on memoization. ;)
Me too since i am new to dp memoization sometimes it's not clear to me :)
Here is the python DP top-down recursive solution with memoization. It took me some time to come up with it.
class Solution:
def __init__(self):
self.memo = {}
self.coins = None
def coinChange(self, coins: List[int], amount: int) -> int:
if self.memo.get(amount) != None:
return self.memo[amount]
if amount == 0:
return 0
if self.coins == None:
self.coins = sorted(coins)
minc = float("inf")
for c in self.coins:
if amount < c:
break
res = self.coinChange(coins=None, amount=amount-c)
if res == -1:
continue
minc = min(res + 1, minc)
res = -1 if minc == float('inf') else minc
self.memo[amount] = res
return res
Dude, your explanation ability is over the top. Amazing!
I don't think this solution would work in all cases.
Let's say you can only use the coins (2, 5, 10) to return a value of 2, at the first iteration and when trying to calculate dp[1] you're gonna find out that no coin is smaller that 1 so the condition "a - c >= 0" will not be met, and so dp[1] will stay equal to amount+1 (and this is gonna screw what comes next). So if you try to know the number of coins needed to return a value of 2 (it should be 1 cause we have 2 in our list of coins), this algorithm will return -1 because you will have dp[2] = amount+1.
I'm not sure if i explained my process of thoughts right, if you think i'm wrong i'd be happy to learn.
Dp2 will be min of maxInt and 1+ dp[2-2] which hits the basecase of 0 and returns 1 correctly
Very well explained. Thank you i finally understood this problem. Keep at it!
Nice and short functional programming style solution:
dp = [0]
for i in range(1, amount+1):
options = [dp[i-x] for x in coins if i >= x and dp[i-x] != -1]
dp.append(-1 if not options else 1+min(options))
return dp[amount]
What is ‘functional’ about this? Also, why constantly resize an array if you know its size (amount+1) ahead to time?
You know without programming this is a question for 5 years old...which coins add up to 7.
Greedy does work if we remove the biggest coin at every full iteration and keep checking for the minimum amount of change. This, however, is pretty inefficient.
i'm from Brazil. And you gained more one subscriber.Because your explanation is very good and you talk so cleary that i can undestand you. And this is so good for me that i'm learning english.
BFS with a Bitmap is also accepted, with the same complexity. Almost the same memory footprint but DP is a lot faster. Sequential memory access is very efficient.
Dude !!!
I don't usually drop comments but this was amazing !
Crisp explanation, thank you soo much.
If you are struggling to understand why we updated dp[i] when (i - coins[j] >= 0) the key insight is that dp[i] only gets updated if there is a solution that leads to zero (even when this condition evaluates to true). That is, there are cases where (i - coins[j] >= 0) but dp[i] remains "amount + 1". For instance if we have amount = 11 and coins = [2, 4, 6], when we get to i = 3, we find that 3 - 2 >= 0. However, min(dp[3], 1 + dp[3 - 2]) causes dp[3] to remain "amount + 1" as there is no valid solution leading to zero that we captured at dp[1] (that is, dp[1] itself still equals "amount + 1").
Good. You can start at min coin value in the outer for loo.
It takes O(len(coins)) extra time to find the min. Helps in cases where amount is too large and number of coins of small.
We can make the code work in constant space complexity by just storing the answer for last five amounts when calculate the current amount.
one of the best solutions and explanation. Even though i knew the solution but still got stunned by your approach........
This is brilliant. Really helped me understand dynamic programming. Thanks!
Mann, my first approach was greedy. Thanks for explaining why it did not work out.
You literally explained this problem better than my algorithms professor at a UC
Great video, deserves at least one million views in my opinion.
Thanks, i appreciate it
Finally found a solution that I can understand. Thank you Sir!
First understand DFS very well, and then try to understand bottom-up DP concept. Coding is trivial, but understanding the whole solution is really hard.
Sick, I tried this for the first time on my own and used BFS to find the "shortest path". Sadly I knew I needed to optimize it with caching but couldn't figure out the right way to implement it. When I saw I only needed 3 extra lines to finish my solution I felt hella dumb. But this is a really good problem.
Thanks again! Your explanation helped a great deal in understanding these complex problems.
I was able to code myself after looking at your video. Great explanation.
Extremely well explained. Thank you so much!
Definitely a confusing one, I hope sometime in the future I understand it better. Thanks for the tip
couple questions: 1. dp[a] = min(dp[a], 1 + dp[a - c]), why should compare itself with 1 + dp[a-c]? is it possible dp[a] it self less than 1 + dp[a- c]? 2. why the condition is if dp[amount] != amount + 1:? if coins = [2], amount = 3, how should it explain under this situation? I am so confused.
Great explanation, regardless I'm still trying to understand the whole concept 😅
Wish I saw this question earlier. I'd have nailed the Intel's coding interview ... Only one that I couldn't solve was this one..
The correct solution on leetcode has ur OUTER loop as its INNER LOOP and your INNER loop as its OUTER loop. Why is it switched around? For example the solution on leetcode says this:
Bottom up DP
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp=[math.inf] * (amount+1)
dp[0]=0
for coin in coins:
for i in range(coin, amount+1):
if i-coin>=0:
dp[i]=min(dp[i], dp[i-coin]+1)
return -1 if dp[-1]==math.inf else dp[-1]
It’s just enumerating the coins first. The time complexity is the same and so is the result, as the correct minimum is still discovered.
self notes: Not greedy - since 5 + 1 + 1 will not work; backtracking - yea but overlapping subproblems so can use DP; Memoization works ; now think in reverse and do bottoms up .
What is the difference between back tracking and dfs? I know dft in graph but how is it used here?
Love the clear and concise explanation!
This can also be solved using breadth-first search since we are trying to find the shortest path from amount to 0.
Thankyou very much. The DFS part is just amazing. It was visually intuitive.
Could you do the DP solution for Partition to K Equal Sum Subsets? There are literally no English explanations for it, only the backtracking approach.
Are the dynamic programming and dfs solutions different in terms of space or time complexity?
Clean and concise explanation. Thanks!
Well explained, bro! Impressive DP solution!
One more thing, if you initialize dp[0] = 1 then you don't need to do 1+ dp[a-c] and this is okay because what is the no of ways to make sum 0 out of n no of coins , the answer is 1 i.e don't consider any coin
Thank you. Your explanation is really clear.
It's a pretty clear solution. really helps me a lot! appreciate!!!
Thank you, very very clear, your videos have very high quality.
Really clear pronunciation! Also the explanations!
crystal clear illustration :) awesome ! Thanks for the video
I think this one should have been discussed with BFS instead of DFS because it's a minimum distance problem.
15:53 This is false!
If you set each value to infinity, it will lead to an overflow when you do the Math.Min(dp[i], dp[i - coins[j]] + 1); That + 1 will cause it to overflow to a large -ve number and that will throw your answer off by a large margin.
Otherwise, you're right it could be any large value BUT with the constraints of the question, the only safe value we can put it amount + 1 since the min denomination of a coin is 1 and that would cause our total number of coins to be at max amount only.
inf+1 is still inf. He is using python not c++
@@sayanghosh6996 Oh, in python it's like that is it? I didn't know. Thanks for the info man.
1 minute of silence for the guys that went into brute force in an interview
Does time complexity differ if we choose top-down dynamic programming?
I think top-down is better because we don't have to compute every number in the range of amount. Am I right?
Was this the very first solution that came to your mind? When I'm seeing these types of solutions, I wonder if there's like ideas eliminated before coming to such a structured solution like this one. I'm posing the question because I wonder if this would be like the first solution you'd think of during a timed technical interview
you can not come up with such a structured solution in an interview setting unless you have done SIMILAR problem before. call it a curse or a blessing , it is what it is.
p.s. i hate it.
Next level explanation! Instantly subscribed! Thank you
What scares me, the bloody solution is not intuitive until and unless you solved/prepared for it.
The key to dynamic programming problems is to find a recursive (top-down) solution first.
Pretty neat explanation man. Thank you
Hi NeetCode. You say that for this problem, you cannot choose a greedy method to solve it. What's an example of a case where you *could* be greedy? Thank you :)
you dont really explain the dp formula from dp[2] to the end
U r just awesome
U make complex solutions easy
Very well explained. I'm a newbie to dp in general, Do people solve these problems off head in interviews? or they just cram the solutions and go for it, because I'm having trouble wrapping my head around these problems.
Great explanation. Crystal clear!
Yo... Kobe...
Amazing explanation man! Thank you so much :)
Just awesome. subscribed your channel. huge love and respect for you bro.
You are the best. Thank you so much for this explanation.