Great explanation! BTW, do you have any idea how we may solve the same problem if we're provided only a limited number of each coin? For example, amount = 5, coins = [1, 2, 5], count = [1, 2, 3] (1 coin of value "1", 2 coins of value "2", 3 coins of value "5")?
@@kevinwang7811 assuming that coins is now a dictionary {denomination:count, ...} ex {2:3, 3:1, 5:2} I came up with the code below. for *each* new coin (denomination AND count), I update the table with itself, shifted by the amount. def changeIterBounded(coins, target): # Seeding the table of ways: No (0) ways to sum up to any amount with no denomination... gTable = [0 for _ in range(target +1)] # ... except for an amount of 0 for which there is only one (1) way gTable[0] = 1 # Populating the table with each of the denominations (and the amount available) for theCoinVal, theCoinCnt in coins.items(): # for each denomination shift the previous table by the new amount (denomination and count) theNewWay = [0] * (len(gTable)) for i in range(1, theCoinCnt +1): # Shift theTempWay = ([0] * theCoinVal * i) + gTable # Truncate the length to the original target theTempWay = theTempWay[:len(gTable)] # consolidate for idx in range(len(gTable)): theNewWay[idx] += theTempWay[idx] # update the original table with the newly found ways. for idx in range(len(gTable)): gTable[idx] = gTable[idx] + theNewWay[idx] return gTable[-1]
And it is also very fun when you learn it. When you will get old, you will get to brag to your nephews and nieces how you learned the Knapsack problem and never ever used it directly.
Hey, just as a heads up you can do an O(n) space dp solution using just one array: dp=[0]*(amount+1) dp[0] = 1 for coin in coins: for i in range(1, amount+1): if i - coin >=0: dp[i] += dp[i-coin] return dp[-1]
Hey! What does the base case dp[0] = 1 mean here? I mean, what does the number zero corresponding to 1 mean in this problem? that to make up 0 amount you need one coin?
Thankyou for explaining using diagram. It was very helpful in understanding the space optimized approach. Below is my bottom up dp iterative solution in Python3: dp = [1] + [0]*amount
for coin in coins: for amount_sum in range(coin, amount + 1): dp[amount_sum] += dp[amount_sum - coin] return dp[-1]
Great explanation! the only input that I want to add is that for the recursive top-down solution, while it can produce the correct answer, the more accurate code that faithfully follows the top-down solution logic should be starting condition for "dfs(0, amount)", then change the base case in dfs(i, a) with following code: "if a == amount" -> "if a == 0" "if a > amount" -> "if a < 0" and change the general case code as follows: "cache[(i,a)] = dfs(i, a + coins[i]) + dfs(i + 1, a)" -> "cache[(i,a)] = dfs(i, a - coins[i]) + dfs(i + 1, a)" The complete code is as follows: class Solution(object): def change(self, amount, coins): """ :type amount: int :type coins: List[int] :rtype: int """ cache = {} def dfs(i, a): if a == 0: return 1 if a < 0: return 0 if i == len(coins): return 0 if (i, a) in cache: return cache[(i,a)] cache[(i,a)] = dfs(i, a - coins[i]) + dfs(i + 1, a) return cache[(i,a)] return dfs(0, amount) the reason why we start with dfs(0, amount) is because in top down approach, we start with the final result value then slowly build our solution from the value amount to value 0(base case)
Explained perfectly Just a minor tweak to use one array solution just update in-place instead of copying. class Solution: def change(self, amount: int, coins: List[int]) -> int: cache = [0]*(amount + 1) cache[0]=1 for coin in coins: for index in range(amount+1): if index-coin>=0: cache[index] += cache[index-coin] return cache[amount]
4:00 another way to look at it is to see that ALL the solutions that have a 1 will be in the first branch. That way you don't need to check again in the branch that starts with 2
Very nice explanation. But I would like to suggest you (from a pedagogical point of view), that it would be better if you had the amounts in the ascending order (left = 0 to right = 5) instead of the other way around, as l2r is the way most people think about arrays.
class Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [1] + [0] * amount for c in coins: for i in range(c, amount + 1): dp[i] += dp[i - c] return dp[-1]
Why does his drawing show an array with three rows but when you run the code it's setup like this? [[1, 1, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
True I have the same question, but it doesn't really matter because when he is filling up the grid, he starts from len(coins) - 1 in the inner loop, so basically the last column of 0s is just added so the logic doesn't go out of bounds and 0 is being used from the extra column.
Think about it. if you don't add the additional column with all 0 values how are you going to add the next value to the 3rd column. Without the additional column the code will throw and error.
At 3:50, in the explanation that was given to prevent duplicates, what would happen if we continue going down the left-most 1 path? If the choices of {1,2,5} are still on the table, how is that logic going to prevent duplicates that start with a 1? For example, [1,1,1,2], [1,1,2,1], and [1,2,1,1]. Wouldn't those 3 sequences show up as distinct paths on that left-most sub-tree of 1? Perhaps I am misunderstanding it, any explanation would be helpful! Great video overall!
Think of [1,1,1,1,1] as the leftmost chain. Now from each of the level in the leftmost chain, you can choose to have only 2 and 5 for the remaining sum (as for any level, 1 is already chosen as its leftmost child). Then all you can have going from left to right and top to bottom: [1,1,1,1,1], [1,1,1,2], [1,2,2],[5]. Basically you are allowed to go down the tree with choice of either coin of your own kind or to next available coin in sequence. From your question above [1,1,1,2], [1,1,2,1], and [1,2,1,1], only [1,1,1,2] is valid as [1,1,2,1] and [1,2,1,1] violate the rule of going back to previous coin "1" when you are at "2". hope it helps.
@NeetCode Can you please split this video and explain each of the solutions separately with a walkthrough of the code. It was difficult to follow this way.
Instead of dp[coin][amount] why can't we just use dp[amount] = number of ways for change? We can say we have all coins available, and it should give the answer still?
3:15 these rules don't guarantee no duplicates. Example: amount = 4 and going down the 1's branch, where 1's and 2's are allowed: 0 -1-> 1 -1-> 2 -2-> 4 : 1+1+2 = 4 0 -1-> 1 -2-> 3 -1-> 4 : 1+2+1 = 4 And we did not touch the 2' branch.
@@NeetCode hey neet, can you tell me the difference between the 2 peoblems. coin change2 and combination sum ? the question is almost the same, but you took 2 different approach for each
In the decision tree for the memoization solution, we're making at most 3 decisions but in the code you're only making 2 decisions. What am I missing here?
So i'm thick as fuck. Somebody remind me in the future to see if i ever get smart and can solve these problems. I've started my DSA journey so we will see
Hi so I tried to do a memoization approach instead of a tabulation approach, where I made a function and in a for loop I went through each index, i, and made a subproblem with amount - coins[i], and starting at index i, for subproblem. I am able to complete this problem, but I realize my approach is very slow compared to a lot of the others I see. I was wondering, does anyone know why that is?
Hey, I just wrote something like that before watching this video. Seems like Neetcode is building from 0 to amount but we went from amount to 0. I don't know why it is so slow.
Replace your for loop with something like this: mem[total][start] = dfs(total - coins[start], start) + dfs(total, start + 1); My time went waaaay shorter. My intuition led me to write a for loop initially like you did too. I still do not grasp why Neetcode wrote it with only 2 recursive calls but it seems like it's closer to the DP matrix filling algo'.
@NeetCode is there an easy way to extend the memoized code to return the actual combinations instead of the number of combinations? I have tried to return [coins[i]] when a==amount. The idea was to extend a list when traversing back up the tree. Didn't quite work.
this was a terrible explanation lol: extremely scattershot, seemingly confusing yourself as you were explaining each step, addressing future problems halfway through the explanation for current problems, etc. It almost feels like you solved the problem 5 minutes before, and realized you had 10 minutes to make the video, but instead of putting it off for another day, you just rushed through it.. Incredibly unlike your usual explanations, which are often concise, structured, and well thought out
![ไข้ขึ้นเลย! เมื่อแฝดโดนจัดเต็มวัคซีนครบ2เดือน🤒 [cc] แดนแพทตี้ SS2 | EP.54 |](http://i.ytimg.com/vi/z2VHItnyyvY/mqdefault.jpg)
This one turned out pretty long, but I hope the timestamps are helpful. Also, the code for all 3 solutions is in the description. 😃
turned out pretty long because your explaination was amazing. keep it up.
Great explanation!
BTW, do you have any idea how we may solve the same problem if we're provided only a limited number of each coin? For example, amount = 5, coins = [1, 2, 5], count = [1, 2, 3] (1 coin of value "1", 2 coins of value "2", 3 coins of value "5")?
Excellent
If I get into Google, I will buy you a beer, and I'm Muslim.
@@kevinwang7811 assuming that coins is now a dictionary {denomination:count, ...} ex {2:3, 3:1, 5:2} I came up with the code below. for *each* new coin (denomination AND count), I update the table with itself, shifted by the amount.
def changeIterBounded(coins, target):
# Seeding the table of ways: No (0) ways to sum up to any amount with no denomination...
gTable = [0 for _ in range(target +1)]
# ... except for an amount of 0 for which there is only one (1) way
gTable[0] = 1
# Populating the table with each of the denominations (and the amount available)
for theCoinVal, theCoinCnt in coins.items():
# for each denomination shift the previous table by the new amount (denomination and count)
theNewWay = [0] * (len(gTable))
for i in range(1, theCoinCnt +1):
# Shift
theTempWay = ([0] * theCoinVal * i) + gTable
# Truncate the length to the original target
theTempWay = theTempWay[:len(gTable)]
# consolidate
for idx in range(len(gTable)):
theNewWay[idx] += theTempWay[idx]
# update the original table with the newly found ways.
for idx in range(len(gTable)):
gTable[idx] = gTable[idx] + theNewWay[idx]
return gTable[-1]
From coin change to coin change 2 it's a big jump pretty big to be honest.. shit man
i have it crazy that interviewers expect you to have never seen this problem and answer it in an hour.
Once you learn the pattern its not to bad.
what company is that? is it a junior role?
You are getting one hour? Here got just 20 mins for these kinds of problems.
This one isn’t so bad. Other questions are much worse; at least you could arrive at this solution by yourself
And it is also very fun when you learn it. When you will get old, you will get to brag to your nephews and nieces how you learned the Knapsack problem and never ever used it directly.
Hey, just as a heads up you can do an O(n) space dp solution using just one array:
dp=[0]*(amount+1)
dp[0] = 1
for coin in coins:
for i in range(1, amount+1):
if i - coin >=0:
dp[i] += dp[i-coin]
return dp[-1]
Hey! What does the base case dp[0] = 1 mean here? I mean, what does the number zero corresponding to 1 mean in this problem? that to make up 0 amount you need one coin?
@@mukundyadav6913 It means that there is 1 way to make $0, which is by having 0 coins.
@@yashbhandari2964 got it thanks!
this is awesome!
fucking wizardry. Makes complete sense seeing it but never would have thought of it.
Thankyou for explaining using diagram. It was very helpful in understanding the space optimized approach.
Below is my bottom up dp iterative solution in Python3:
dp = [1] + [0]*amount
for coin in coins:
for amount_sum in range(coin, amount + 1):
dp[amount_sum] += dp[amount_sum - coin]
return dp[-1]
Great explanation! the only input that I want to add is that for the recursive top-down solution, while it can produce the correct answer,
the more accurate code that faithfully follows the top-down solution logic should be starting condition for "dfs(0, amount)", then change the base case in dfs(i, a) with following code:
"if a == amount" -> "if a == 0"
"if a > amount" -> "if a < 0"
and change the general case code as follows:
"cache[(i,a)] = dfs(i, a + coins[i]) + dfs(i + 1, a)" -> "cache[(i,a)] = dfs(i, a - coins[i]) + dfs(i + 1, a)"
The complete code is as follows:
class Solution(object):
def change(self, amount, coins):
"""
:type amount: int
:type coins: List[int]
:rtype: int
"""
cache = {}
def dfs(i, a):
if a == 0:
return 1
if a < 0:
return 0
if i == len(coins):
return 0
if (i, a) in cache:
return cache[(i,a)]
cache[(i,a)] = dfs(i, a - coins[i]) + dfs(i + 1, a)
return cache[(i,a)]
return dfs(0, amount)
the reason why we start with dfs(0, amount) is because in top down approach, we start with the final result value then slowly build our solution from the value amount to value 0(base case)
Explained perfectly
Just a minor tweak to use one array solution
just update in-place instead of copying.
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
cache = [0]*(amount + 1)
cache[0]=1
for coin in coins:
for index in range(amount+1):
if index-coin>=0:
cache[index] += cache[index-coin]
return cache[amount]
4:00 another way to look at it is to see that ALL the solutions that have a 1 will be in the first branch. That way you don't need to check again in the branch that starts with 2
Very nice explanation. But I would like to suggest you (from a pedagogical point of view), that it would be better if you had the amounts in the ascending order (left = 0 to right = 5) instead of the other way around, as l2r is the way most people think about arrays.
Thanks for the video! Could you also cover 'Minimum Cost For Tickets' which is one of DP problems chosen from you?
Thanks for the video! I had to draw out the recursion tree of your solution to really understand it. Definitely a more challenging problem
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [1] + [0] * amount
for c in coins:
for i in range(c, amount + 1):
dp[i] += dp[i - c]
return dp[-1]
Great explanation!
You can further improve the space complexity (O(n)) by:
#might need to do coins.sort()
dp=[0]*(amount+1)
dp[0]=1
for coin in coins:
for value in range(coin,amount+1):
dp[value]+=dp[value-coin]
return dp[-1]
The code and the graph you draw is reversed direction, was hard to figure out already
Why does his drawing show an array with three rows but when you run the code it's setup like this?
[[1, 1, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
True I have the same question, but it doesn't really matter because when he is filling up the grid, he starts from len(coins) - 1 in the inner loop, so basically the last column of 0s is just added so the logic doesn't go out of bounds and 0 is being used from the extra column.
Think about it. if you don't add the additional column with all 0 values how are you going to add the next value to the 3rd column. Without the additional column the code will throw and error.
Hmm, the coins order have be ascending ordered (from lowest to highest), instead the DP solution won't pass test case where coins=[99,1]
I fail to understand the table that is introduced at 8:05 .
this should be named coin change 4 lol
It will be better if you can explain the recursion solution code with the illustration together.
great explanation = thank you so much + please continue❤❤❤
At 3:50, in the explanation that was given to prevent duplicates, what would happen if we continue going down the left-most 1 path? If the choices of {1,2,5} are still on the table, how is that logic going to prevent duplicates that start with a 1? For example, [1,1,1,2], [1,1,2,1], and [1,2,1,1]. Wouldn't those 3 sequences show up as distinct paths on that left-most sub-tree of 1? Perhaps I am misunderstanding it, any explanation would be helpful! Great video overall!
Think of [1,1,1,1,1] as the leftmost chain. Now from each of the level in the leftmost chain, you can choose to have only 2 and 5 for the remaining sum (as for any level, 1 is already chosen as its leftmost child). Then all you can have going from left to right and top to bottom: [1,1,1,1,1], [1,1,1,2], [1,2,2],[5]. Basically you are allowed to go down the tree with choice of either coin of your own kind or to next available coin in sequence. From your question above [1,1,1,2], [1,1,2,1], and [1,2,1,1], only [1,1,1,2] is valid as [1,1,2,1] and [1,2,1,1] violate the rule of going back to previous coin "1" when you are at "2". hope it helps.
@@oswald3042 it does not help
correct me if im wrong, but [1,1,2,1], and [1,2,1,1] are not valid paths, because once you choose '2', you cannot go back and choose '1'
how important is it to do bottom up approach vs memorization for interviews?
Im struggling to understand the difference between DP and just recursion/iteration with memoization
I have Amazon interviews this week. I hope I will crack it.
Did you crack it?😀
Ig he cracked his neck....
Why do we need nextDP? if you are setting nextdp[a] = dp[a] every sub iteration might as well just use dp in the first place?
This explanation was very difficult for me to understand, as it sounded a bit disorganized. Appreciate the upload regardless
@NeetCode Can you please split this video and explain each of the solutions separately with a walkthrough of the code. It was difficult to follow this way.
Thanks, it really helps me a lot!
"And this path, will never have any(one)" 4:05😢
lol
Instead of dp[coin][amount] why can't we just use dp[amount] = number of ways for change?
We can say we have all coins available, and it should give the answer still?
3:15 these rules don't guarantee no duplicates. Example: amount = 4 and going down the 1's branch, where 1's and 2's are allowed:
0 -1-> 1 -1-> 2 -2-> 4 : 1+1+2 = 4
0 -1-> 1 -2-> 3 -1-> 4 : 1+2+1 = 4
And we did not touch the 2' branch.
It's applied recursively, so going down the top level 1 branch, when 2 is selected, 1s are no longer allowed.
I'm living on your channel~~❥
this question is medium?? wowwwwwww
Agree, it's pretty hard for a medium
@@NeetCode hey neet, can you tell me the difference between the 2 peoblems. coin change2 and combination sum ? the question is almost the same, but you took 2 different approach for each
why is the base case for amount 0 is 1? since you can't use any coin, it should be 0 right?
In the decision tree for the memoization solution, we're making at most 3 decisions but in the code you're only making 2 decisions. What am I missing here?
The Decisions we are making is basically to pick the coin or to skip the coin... Therefore we only have two choice...
You probably need to watch the Combination Sum problem explanation, hopefully it should make things clear
don't understand the skipping the current index in the memoization approach and it wasn't explained before the code. anyone knows the reason?
So i'm thick as fuck. Somebody remind me in the future to see if i ever get smart and can solve these problems. I've started my DSA journey so we will see
great video btw
Hi so I tried to do a memoization approach instead of a tabulation approach, where I made a function and in a for loop I went through each index, i, and made a subproblem with amount - coins[i], and starting at index i, for subproblem. I am able to complete this problem, but I realize my approach is very slow compared to a lot of the others I see. I was wondering, does anyone know why that is?
Hey, I just wrote something like that before watching this video. Seems like Neetcode is building from 0 to amount but we went from amount to 0. I don't know why it is so slow.
Replace your for loop with something like this: mem[total][start] = dfs(total - coins[start], start) + dfs(total, start + 1);
My time went waaaay shorter. My intuition led me to write a for loop initially like you did too. I still do not grasp why Neetcode wrote it with only 2 recursive calls but it seems like it's closer to the DP matrix filling algo'.
Done the same thing. The neetcode recursion approach doesnt match the diagram that he drew. It matches the tree diagram in the LeetCode's solution.
don't understand whats yourt mechanism to avoid dupes
excellent!
@NeetCode is there an easy way to extend the memoized code to return the actual combinations instead of the number of combinations?
I have tried to return [coins[i]] when a==amount. The idea was to extend a list when traversing back up the tree. Didn't quite work.
here is the 1D c++ DP:
int change(int amount, std::vector& coins) {
std::vector mem(amount + 1, 0);
mem[0] = 1;
for(int coin: coins) {
for(int i = 0; i = 0){
mem[i] += mem[i-coin];
}
}
}
return mem[amount];
}
or,
int change(int amount, std::vector& coins){
std::vector mem(amount + 1, 0);
mem[0] = 1; // 1 way to make 0 coins
for(int coin : coins){
for(int i = coin; i
this was a terrible explanation lol: extremely scattershot, seemingly confusing yourself as you were explaining each step, addressing future problems halfway through the explanation for current problems, etc.
It almost feels like you solved the problem 5 minutes before, and realized you had 10 minutes to make the video, but instead of putting it off for another day, you just rushed through it..
Incredibly unlike your usual explanations, which are often concise, structured, and well thought out
"terrible" is an insane stretch it was overall still very much intelligible. But yeah it was more scattershot than usual
disagree, maybe if you skipped coin change 1
Although the coding part was rushed through, the explanation is pretty solid and clear if you have solved and understood Coin Change 1.
function change(amount, coins) {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (const coin of coins) {
for (let i = coin; i
I feel sympathetic when I first encountered this problem and even couldn't write a brute force 🥲