Coin Change 2 | Dynamic programming | Leetcode
HTML-код
- Опубликовано: 6 июн 2020
- This video explains a very important dynamic programming interview problem which is to find the number of possible ways to form a given amount using the given coin denominations having infinite instances of each coin denomination.We can solve this problem using recursion but the time complexity will be exponential.I have shown how we can convert this problem to a dynamic programming problem using the properties of optimal substructure and repeating subproblems.I have shown the solution for dynamic programming using proper examples.At the end of the video,i have
shown the code walkthrough and have also shown how to optimize the dynamic programming using just one dimensional array maintaining just a single row.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
=================================================================
INSTAGRAM: / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
=================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
This has to be one of the best explanation of DP.
Thanks :)
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 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 am following some courses for DSA but for a clear understanding, I repeatedly have to come back here. You have something.😁
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 😃
Very helpful video 😊
I see many time of interview this question was asked
Thank you so much for providing this solution
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 :(
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
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.
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 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. ^_^
Honestly your dp approach is what everyone should follow, It's simple but powerful. Thanks a lot Techdose
JAVA Solution - github.com/neeraj11789/tech-interview-problems/blob/db63845ae0a24835f9edc8703e268d146cfa56d4/src/main/java/leetcode/junechallenge/CoinChange2.java
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.
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?
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.
Sir Thank you. Literally, u saved me. Thank you again.
Welcome :)
Thank you so much for the clear explanation!
Welcome :)
thanks a lot man! very well explained.
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❤❤
God bless u man. You are such a saviour. 👏🙏🙏
Welcome
Sir what is the intuition for O(n) sc.... I mean why this algo work?
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.
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 :)
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
Thanks a lot TechDose!
Welcome :)
Amazing explanation!!
Thanks :)
This is beautiful
What a good explanation. Thanks a lot
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
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 :)
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
I have a question for this problem, what if the order matter. Ex: 5 = 2 + 2 + 1 = 1 + 2 + 2 = 2 + 1 + 2
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
}
👍
Very nicely explained.
Thanks
Good show!
👍
Can you help me with a scenario where amount is not absolute like amount is 15.05.
Thanks man you're my best friend
Welcome :)
Good work 💯
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 😅
you are my best in the youtuber
It means a lot :)
thanks alot man
Welcome
Amazing Dude
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
bhai ! tum gazab ho !
Thanks 😅
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.
This is amazing
Thanks
What will be the time complexity of 1D solution
But what if the amount is large
Brilliant
Thanks :)
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.
Sir :) 🙏
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
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
👍
👍
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]
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.
please also make coin change 1
Yes I surely will in future
The most famous problem
Yea....one of the important.
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.
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
Linear DP solution with meaningful comments. O(n) Space
leetcode.com/submissions/detail/445825375/
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
👍🏼
Explanation was off and not at all clear starting from 7.10 thru 13.16. Hence, didn't watch after that.
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
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
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.