This was a very well thought out and explained approach to solving dp problems! Other channels quickly go over the 2D array but don't explain how it's made.... I still need more practice to do this on my own 100%, but thanks!
Great work! I am currently struggling to clear interviews(I had amazon onsite,Bloomberg onsite and Expedia just last week!), just unable to cross the last hurdle, probably need to iron out a lot of my code, since I start from brute force and then end up with an optimal solution, your channel is helping me work on my confidence again!.
I have gone through many solutions for this question explained by others, But, Your explanation is way more acceptable and understandable for even basic concepts used in between of solution. Thanks a lot for this explanation. Have a good luck !
Thanks for your explanation Took me a while, but I finally got what you were saying. I'm actually surprised at how close I got on this using recursion. - I set things up to recurse with each new coin denomination, and tried each possible # of coins of the current type. In that manner I avoided duplicate subcases. - I got a TLE on this guy: 500 [3,5,7,8,9,10,11], which I solved by pre-processing the coins to pair up coins with integral denomination ratios. In this case, I managed to get rid of 9 and 10. - Then I ran into this: 5000 [11, 24, 37, 50, 63, 76, 89, 102], which had something like 18 quadrillion possible combinations. I thought there was some significance to the spacing of 13 between each denomination, but I couldn't figure out how to make use of that :(
I can see how subset sum count, and coin change 2 is related. basically it comes down to inclusion and exclusion. After watching 10 videos on dp, i have gained confidence in solving dp problems. Thanks techdose. ^_^
The concept at 6:37 took a few watches to understand... and im still confused. I understand conceptually you are finding out "how many ways to reach certain value, and another value, then adding them up to a new value" in order to avoid repeating sub answers, the dp 2d array part is where I always get lost bc abstractly connecting the logic behind WHY this all works with the basic logic of what to put where while iterating through the array doesn't click. I'm really trying to get a grasp for DP, by studying the recursive structure (slow), the enhanced recursive structure (faster, saving old values to remove repetition), and finally the DP[m][n] and DP[2, n] (with the flag^1 approach for lowered memory) and trying to connect them all. This is the hardest type of problem solving I want to master.
This is a hard problem. If someone did not work on this problem before, and if they automatically derived this formula in 30 minutes of interview by themselves, they are god level. Really dont understand why interviewers ask such questions in interviews and expect this to be solved in optimal time complexity in 30 minutes.
That is a good point. However, you would notice that there is an aspect of either "including/excluding condition" mentioned in the video. This is an essential step to solving 'grouping' problems with dynamic programming (more/less derivable to the more general Knapsack problem). Not surprisingly, there are significant tricks to solving some of these problems with guided practice and understanding, which TECH DOSE has done an incredible job at explaining. Another example would be to start solving recursive problems, by first forming the recurrence relation.
Hi, I had gone through many videos regarding the same problem but wasn't able to understand how they had filled the dp table. Your video made it crystal clear. Thank you. can you tell me how do i solve the same problem if it asks for all the combinations like (1,2,2),(2,2,1),(2,1,2)-->> all these are different combinations just like the question Combination Sum 4 in leetcode.
thank you so much sir. I am not going to write a comment more than this because if i started to write comment on your explanation its not going to end. thank you sir once again from bottom of my hart❤❤
what if we dont start from 0th index whenevr we call recursion and we start from the called value's index .i.e, when we start from 2(1st level) we dont visit 1(2nd level) but start from 2 itself... similarly when we start at 5 (1st level) we dont go for 1 , 2 (2nd level) and start from 5.... we do this in all subsequent call... what will be the time complexity for this?
Again a nice explaination Sir, its a good problem on unbounded knapsack, i tried using recursion with memoization :- int dp[500][5001];
int solve(int arr[], int k, int n) { if(n==0) // if number of coins is 0, if amount is zero then return 1 return (k==0);
else if(k==0) // if amount is zero , return 1 return 1;
else if(arr[n]>k) // if current coin value is grater than required amount, can not include recur for next coin return solve(arr,k,n-1);
else if(dp[n][k]!=-1) // if result of current (coin,amount) is already calculated and stored, return the stored result return dp[n][k];
else return dp[n][k]=(solve(arr,k,n-1)+solve(arr,k-arr[n],n)); // otherwise, we have two choices, 1.) leave this coin move to next coin, 2.) include this coin and as no limit on coin use so recur for same coin }
I think time complexity of the recursive solution (without dp) will be O(amount ^ no. of coins) and for every amount we will make no 'n' no of choices, where n is no. of coins. Correct me if I'm wrong :)
No no. You will see how many choices you have at a particular recursion call and you will use a loop to cover all choices. For each choice you again make a recursion call. As I said, find max recursion depth. So you need to make your choices that many times. So according to given example, it will be 3*3*....*3(Depth times).
Leetcode - 322 coin change had first column with zeros. But this one is being filled with ones. Can you explain ? Better to have consistent base case for all knapsack type problems
In leetcode 322 in column 0 for example take dp[2][0] how many coins we needed to make amount 0 with 2 coins it's zero right with zero coins we can make amount 0 and same for all in that column so sir filled 0 in that problem... But in this problem it's a slight difference, how many ways we needed to make the amount 0... for the same example dp[2][0] we have 1 way to make the amount 0 if we have 2 coins that we exclude both coins ... there is 1 way so in this problem in column 0 it was filled with 1... I hope you understood
First of all Thank you for educating us. I solved the problem in same approach where the time complexity is O(n2). Failing for the larger test set. Could you please confirm
Sir, can you give the appraoch for this question in O(n) space? I solved this question on another platform with the help of your explanation but its asking for O(n) space complexity.
I'm having trouble getting the intuition why finding combination problems requires us thinking about including/not-including subproblems, whereas problems for finding permutations (like Combination Sum IV) don't.
sir, if you can give ample amount of time for code walkthrough, along with explanation , that would be of much help .Otherwise, your content is very good.
Thank you so much for the video Sir.your ideas are always crystal clear can you please tell how and in which websites did you practice and improved your coding skills?
Then it's a much easier problem. Make a 1D array of size Amount. Say Array[1...Amount] Set Array[c]=1 if c in Coins. For i in {1,Amount} For c in Coins Array[i]+=Array[i-c] Return Array[Amount]
I guess this is a recursion implementation, but it get time limit exceeded. class Solution { public: int count = 0; int value = 0; void way(int curr,int sum, vector& coins) { if(curr == coins.size()) return; if(sum > value) return; if(value == sum) { count++; return; } for(int i=curr;i
Solution is provided, but when explaining the dp approach, it is not so clear. Seems like some paragraph reading from a coding website. Please improve in why this particular approach is used and how we are moving towards it.
Yes this will help. If you are not able to solve then try to atleast implement the idea after watching so that when this type of question repeats then you find yourself in good position for solving this.
ing, Integer> memoizationCache = new HashMap(); static int[] denomination = new int[]{1, 2, 3}; public static int makeChange(int denominationIndex, int target) { if (memoizationCache.containsKey(denominationIndex + "," + target)) { return memoizationCache.get(denominationIndex + "," + target); } int choiceTake = 0; int choiceLeave; int optimal; int coinValue = denomination[denominationIndex]; //choiceTake: the total least number of coins we need if we choose to take a coin if (target < coinValue) { //coin to large choiceTake = Integer.MAX_VALUE; } else if (coinValue == target) { //value reached choiceTake = 1; } else if (coinValue < target) { //take 1 coin and recurse choiceTake = 1 + makeChange(denominationIndex, target - coinValue); } //choiceLeave: the total least number of coins we need if we choose to leave the current a coin denomination if (denominationIndex == 0 || coinValue == target) { choiceLeave = Integer.MAX_VALUE; } else { choiceLeave = makeChange(denominationIndex - 1, target); } optimal = Math.min(choiceLeave, choiceTake); memoizationCache.put(denominationIndex + "," + target, optimal); return optimal; }
Solution is provided, but when explaining the dp approach, it is not so clear. Seems like some paragraph reading from a coding website. Please improve in why this particular approach is used and how we are moving towards it.
This was a very well thought out and explained approach to solving dp problems!
Other channels quickly go over the 2D array but don't explain how it's made.... I still need more practice to do this on my own 100%, but thanks!
This has to be one of the best explanation of DP.
Thanks :)
I am following some courses for DSA but for a clear understanding, I repeatedly have to come back here. You have something.😁
Honestly your dp approach is what everyone should follow, It's simple but powerful. Thanks a lot Techdose
This is called teaching....not like other channel where they just show off by writing code in one or two minutes!!!
😅 thanks
Great work! I am currently struggling to clear interviews(I had amazon onsite,Bloomberg onsite and Expedia just last week!), just unable to cross the last hurdle, probably need to iron out a lot of my code, since I start from brute force and then end up with an optimal solution, your channel is helping me work on my confidence again!.
Nice. Keep practicing :)
You’re amazing! - I struggled to understand this problem until your video! Thanks for supplying this content 👍🏼
Welcome :)
I have gone through many solutions for this question explained by others, But, Your explanation is way more acceptable and understandable for even basic concepts used in between of solution. Thanks a lot for this explanation. Have a good luck !
I just want to say thank you so much for your help Sir. Your videos have been helping me so much to understand those dp problems.
Welcome 😃
Thanks for your explanation Took me a while, but I finally got what you were saying.
I'm actually surprised at how close I got on this using recursion.
- I set things up to recurse with each new coin denomination, and tried each possible # of coins of the current type. In that manner I avoided duplicate subcases.
- I got a TLE on this guy: 500 [3,5,7,8,9,10,11], which I solved by pre-processing the coins to pair up coins with integral denomination ratios. In this case, I managed to get rid of 9 and 10.
- Then I ran into this: 5000 [11, 24, 37, 50, 63, 76, 89, 102], which had something like 18 quadrillion possible combinations. I thought there was some significance to the spacing of 13 between each denomination, but I couldn't figure out how to make use of that :(
I can see how subset sum count, and coin change 2 is related. basically it comes down to inclusion and exclusion. After watching 10 videos on dp, i have gained confidence in solving dp problems. Thanks techdose. ^_^
Got a really good understanding of this problem by watching this in combination with Back to Back SWE's video on this question. Thanks
Welcome
The concept at 6:37 took a few watches to understand... and im still confused. I understand conceptually you are finding out "how many ways to reach certain value, and another value, then adding them up to a new value" in order to avoid repeating sub answers, the dp 2d array part is where I always get lost bc abstractly connecting the logic behind WHY this all works with the basic logic of what to put where while iterating through the array doesn't click.
I'm really trying to get a grasp for DP, by studying the recursive structure (slow), the enhanced recursive structure (faster, saving old values to remove repetition), and finally the DP[m][n] and DP[2, n] (with the flag^1 approach for lowered memory) and trying to connect them all. This is the hardest type of problem solving I want to master.
God bless u man. You are such a saviour. 👏🙏🙏
Welcome
This is a hard problem.
If someone did not work on this problem before, and if they automatically derived this formula in 30 minutes of interview by themselves, they are god level.
Really dont understand why interviewers ask such questions in interviews and expect this to be solved in optimal time complexity in 30 minutes.
Just to filter candidates and no other reason 😅
That is a good point. However, you would notice that there is an aspect of either "including/excluding condition" mentioned in the video. This is an essential step to solving 'grouping' problems with dynamic programming (more/less derivable to the more general Knapsack problem). Not surprisingly, there are significant tricks to solving some of these problems with guided practice and understanding, which TECH DOSE has done an incredible job at explaining. Another example would be to start solving recursive problems, by first forming the recurrence relation.
I am able to understand each and every concept that you deliver. Thanks a lot!
please make a video on coin change problem where order matters.
Sure I will make it when I cover DP
Hi,
I had gone through many videos regarding the same problem but wasn't able to understand how they had filled the dp table. Your video made it crystal clear. Thank you.
can you tell me how do i solve the same problem if it asks for all the combinations like (1,2,2),(2,2,1),(2,1,2)-->> all these are different combinations just like the question Combination Sum 4 in leetcode.
thank you so much sir.
I am not going to write a comment more than this because if i started to write comment on your explanation its not going to end.
thank you sir once again from bottom of my hart❤❤
Very helpful video 😊
I see many time of interview this question was asked
Thank you so much for providing this solution
Sir Thank you. Literally, u saved me. Thank you again.
Welcome :)
you are my best in the youtuber
It means a lot :)
You sir, Is a G.O.A.T 🔥
GOAT! 😅 What is that
@@techdose4u Greatest of all the time ! 💯 & Dats you mate 💗
Thanks for such praisal 😅
what if we dont start from 0th index whenevr we call recursion and we start from the called value's index .i.e,
when we start from 2(1st level) we dont visit 1(2nd level) but start from 2 itself... similarly when we start at 5 (1st level) we dont go for 1 , 2 (2nd level) and start from 5.... we do this in all subsequent call...
what will be the time complexity for this?
Good work 💯
Sir what is the intuition for O(n) sc.... I mean why this algo work?
Can you help me with a scenario where amount is not absolute like amount is 15.05.
What will be the time complexity of 1D solution
Again a nice explaination Sir, its a good problem on unbounded knapsack, i tried using recursion with memoization :-
int dp[500][5001];
int solve(int arr[], int k, int n)
{
if(n==0) // if number of coins is 0, if amount is zero then return 1
return (k==0);
else if(k==0) // if amount is zero , return 1
return 1;
else if(arr[n]>k) // if current coin value is grater than required amount, can not include recur for next coin
return solve(arr,k,n-1);
else if(dp[n][k]!=-1) // if result of current (coin,amount) is already calculated and stored, return the stored result
return dp[n][k];
else
return dp[n][k]=(solve(arr,k,n-1)+solve(arr,k-arr[n],n)); // otherwise, we have two choices, 1.) leave this coin move to next coin, 2.) include this coin and as no limit on coin use so recur for same coin
}
👍
What a good explanation. Thanks a lot
Welcome :)
I think time complexity of the recursive solution (without dp) will be O(amount ^ no. of coins) and for every amount we will make no 'n' no of choices, where n is no. of coins. Correct me if I'm wrong :)
No no. You will see how many choices you have at a particular recursion call and you will use a loop to cover all choices. For each choice you again make a recursion call. As I said, find max recursion depth. So you need to make your choices that many times. So according to given example, it will be 3*3*....*3(Depth times).
@@techdose4u Got it! Thank you
Welcome :)
Very nicely explained.
Thanks
Thanks a lot TechDose!
Welcome :)
Leetcode - 322 coin change had first column with zeros. But this one is being filled with ones. Can you explain ? Better to have consistent base case for all knapsack type problems
In leetcode 322 in column 0 for example take dp[2][0] how many coins we needed to make amount 0 with 2 coins it's zero right with zero coins we can make amount 0 and same for all in that column so sir filled 0 in that problem... But in this problem it's a slight difference, how many ways we needed to make the amount 0... for the same example dp[2][0] we have 1 way to make the amount 0 if we have 2 coins that we exclude both coins ... there is 1 way so in this problem in column 0 it was filled with 1... I hope you understood
Thanks man you're my best friend
Welcome :)
First of all Thank you for educating us. I solved the problem in same approach where the time complexity is O(n2). Failing for the larger test set. Could you please confirm
No, why will it fail. It is running fine. Are you getting wrong answer? If so, then check your conditional statements. There might be something wrong.
Sir, can you give the appraoch for this question in O(n) space? I solved this question on another platform with the help of your explanation but its asking for O(n) space complexity.
You should try taking a 1D vector and use the same equation for the same vector. Think. You will get it.
@@techdose4u ok sir
I'm having trouble getting the intuition why finding combination problems requires us thinking about including/not-including subproblems, whereas problems for finding permutations (like Combination Sum IV) don't.
Coin change is a knapsack problem
Thank you so much for the clear explanation!
Welcome :)
Amazing explanation!!
Thanks :)
thanks a lot man! very well explained.
1D DP solution in Python:
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for i in coins:
for j in range(1, amount + 1):
if (j >= i):
dp[j] += dp[j - i]
return dp[amount]
sir can we do in o(n) space complexity
Yes correct because you need to maitain just the previous state and update elements from beginning to end.
@@techdose4u i didn' tget sir can you elaborate
Amazing Dude
I have a question for this problem, what if the order matter. Ex: 5 = 2 + 2 + 1 = 1 + 2 + 2 = 2 + 1 + 2
sir, if you can give ample amount of time for code walkthrough, along with explanation , that would be of much help .Otherwise, your content is very good.
Sure I will try to explain more
Thank you so much for the video Sir.your ideas are always crystal clear
can you please tell how and in which websites did you practice and improved your coding skills?
Geeksforgeeks
@@techdose4u thank you sir
Welcome :)
bhai ! tum gazab ho !
Thanks 😅
Sir ,how to print the possible ways
input : [1,2,5] amount=[5]
output:
1,1,1,1,1
1,1,1,2
2,2,1
5
But what if the amount is large
Good show!
👍
This is amazing
Thanks
what is time complexity?
amount x number of coins.
What to do if 1 1 1 1 2 and 2 1 1 1 1 are both allowed in answer?
Then it's a much easier problem.
Make a 1D array of size Amount.
Say Array[1...Amount]
Set Array[c]=1 if c in Coins.
For i in {1,Amount}
For c in Coins
Array[i]+=Array[i-c]
Return Array[Amount]
Change the condition. Tweak some points in the code and you will manage to do it. Try to tweak and test your code.
In which company you are in
And what are your classification
Sorry for the personal question
But i want to know, 🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Follow on linkedIn
@@techdose4u by which name you are in linked in
@@asktostranger8296 Go to channels about tab.
He is working at Samsung R n D
I guess this is a recursion implementation, but it get time limit exceeded.
class Solution {
public:
int count = 0;
int value = 0;
void way(int curr,int sum, vector& coins) {
if(curr == coins.size()) return;
if(sum > value) return;
if(value == sum) {
count++;
return;
}
for(int i=curr;i
This is beautiful
The most famous problem
Yea....one of the important.
thanks alot man
Welcome
Brilliant
Thanks :)
JAVA Solution - github.com/neeraj11789/tech-interview-problems/blob/db63845ae0a24835f9edc8703e268d146cfa56d4/src/main/java/leetcode/junechallenge/CoinChange2.java
please also make coin change 1
Yes I surely will in future
Linear DP solution with meaningful comments. O(n) Space
leetcode.com/submissions/detail/445825375/
👍
👍
Sir :) 🙏
:)
using 1d array
class Solution {
public int change(int amount, int[] coins) {
int dp[] = new int[amount+1];
dp[0] = 1;
for(int i=0;i
👍🏼
I did it using 1-d array :-
class Solution {
public:
int change(int amount, vector& coins) {
int dp[5001]={0};
dp[0]=1;
for(int i=0;i
Solution is provided, but when explaining the dp approach, it is not so clear. Seems like some paragraph reading from a coding website. Please improve in why this particular approach is used and how we are moving towards it.
Man im not able to solve problems on my own I just come to k ow logic by the videos and then write code anything can help me with this?
Yes this will help. If you are not able to solve then try to atleast implement the idea after watching so that when this type of question repeats then you find yourself in good position for solving this.
Java Solution
class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount+1];
dp[0] =1;
for(int i=0;i
Explanation was off and not at all clear starting from 7.10 thru 13.16. Hence, didn't watch after that.
ing, Integer> memoizationCache = new HashMap();
static int[] denomination = new int[]{1, 2, 3};
public static int makeChange(int denominationIndex, int target) {
if (memoizationCache.containsKey(denominationIndex + "," + target)) {
return memoizationCache.get(denominationIndex + "," + target);
}
int choiceTake = 0;
int choiceLeave;
int optimal;
int coinValue = denomination[denominationIndex];
//choiceTake: the total least number of coins we need if we choose to take a coin
if (target < coinValue) {
//coin to large
choiceTake = Integer.MAX_VALUE;
} else if (coinValue == target) {
//value reached
choiceTake = 1;
} else if (coinValue < target) {
//take 1 coin and recurse
choiceTake = 1 + makeChange(denominationIndex, target - coinValue);
}
//choiceLeave: the total least number of coins we need if we choose to leave the current a coin denomination
if (denominationIndex == 0 || coinValue == target) {
choiceLeave = Integer.MAX_VALUE;
} else {
choiceLeave = makeChange(denominationIndex - 1, target);
}
optimal = Math.min(choiceLeave, choiceTake);
memoizationCache.put(denominationIndex + "," + target, optimal);
return optimal;
}
Solution is provided, but when explaining the dp approach, it is not so clear. Seems like some paragraph reading from a coding website. Please improve in why this particular approach is used and how we are moving towards it.