Coin Change 2 | Dynamic programming | Leetcode

[@AtulDislay]

This has to be one of the best explanation of DP.

[@techdose4u]

Thanks :)

[@dorondavid4698]

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!

[@NiteshSingh5375]

I am following some courses for DSA but for a clear understanding, I repeatedly have to come back here. You have something.😁

[@slimysnail6071]

Honestly your dp approach is what everyone should follow, It's simple but powerful. Thanks a lot Techdose

[@psps4754]

This is called teaching....not like other channel where they just show off by writing code in one or two minutes!!!

[@techdose4u]

😅 thanks

[@haydnmurray6998]

You’re amazing! - I struggled to understand this problem until your video! Thanks for supplying this content 👍🏼

[@techdose4u]

Welcome :)

[@kumarkislay9632]

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 !

[@shaileshhegde9205]

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!.

[@techdose4u]

Nice. Keep practicing :)

[@crankyinmv]

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 :(

[@yitingg7942]

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.

[@techdose4u]

Welcome 😃

[@dayanandraut5660]

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. ^_^

[@mohituniyal3008]

Got a really good understanding of this problem by watching this in combination with Back to Back SWE's video on this question. Thanks

[@techdose4u]

Welcome

[@dataman4503]

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.

[@techdose4u]

Just to filter candidates and no other reason 😅

[@urbancoder96]

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.

[@darshandarshan-ph6uk]

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❤❤

[@codingexception6502]

God bless u man. You are such a saviour. 👏🙏🙏

[@techdose4u]

Welcome

[@rehanakhter4813]

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.

[@techdose4u]

Sure I will make it when I cover DP

[@openworld7585]

you are my best in the youtuber

[@techdose4u]

It means a lot :)

[@012_amar_sarkar9]

Good work 💯

[@michaellieberman114]

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.

[@kunalsoni7681]

Very helpful video 😊 I see many time of interview this question was asked Thank you so much for providing this solution

[@aparajitchatterjee3672]

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.

[@rishikeshmishra715]

Sir Thank you. Literally, u saved me. Thank you again.

[@techdose4u]

Welcome :)

[@shivatomar4319]

You sir, Is a G.O.A.T 🔥

[@techdose4u]

GOAT! 😅 What is that

[@shivatomar4319]

@@techdose4u Greatest of all the time ! 💯 & Dats you mate 💗

[@techdose4u]

Thanks for such praisal 😅

[@divyagowda836]

Very nicely explained.

[@techdose4u]

Thanks

[@ShreyaSingh-vr9qi]

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 }

[@techdose4u]

👍

[@giorgi23]

What a good explanation. Thanks a lot

[@techdose4u]

Welcome :)

[@manojjain3501]

Amazing Dude

[@akhilkumarp]

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]

[@suharajsalim4549]

Thanks a lot TechDose!

[@techdose4u]

Welcome :)

[@himanshupanwar2819]

thanks a lot man! very well explained.

[@santhoshjallu926]

Thanks man you're my best friend

[@techdose4u]

Welcome :)

[@mallikakejriwal3729]

bhai ! tum gazab ho !

[@techdose4u]

Thanks 😅

[@nishant_raj312]

Amazing explanation!!

[@techdose4u]

Thanks :)

[@minhdang5132]

Thank you so much for the clear explanation!

[@techdose4u]

Welcome :)

[@subham-raj]

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 :)

[@techdose4u]

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).

[@subham-raj]

@@techdose4u Got it! Thank you

[@techdose4u]

Welcome :)

[@BoobalanMunusamy]

Good show!

[@techdose4u]

👍

[@venothanand91]

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

[@techdose4u]

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.

[@anirudhdevpura2798]

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.

[@techdose4u]

Sure I will try to explain more

[@babacargadiaga4171]

This is amazing

[@techdose4u]

Thanks

[@F34R303]

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.

[@techdose4u]

Coin change is a knapsack problem

[@princeanthony8525]

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

[@jalanubha]

Brilliant

[@techdose4u]

Thanks :)

[@julianbullmagic]

This is beautiful

[@CollectConnectDots]

JAVA Solution - github.com/neeraj11789/tech-interview-problems/blob/db63845ae0a24835f9edc8703e268d146cfa56d4/src/main/java/leetcode/junechallenge/CoinChange2.java

[@AnkitSingh-zj2uc]

The most famous problem

[@techdose4u]

Yea....one of the important.

[@cocoarecords]

thanks alot man

[@techdose4u]

Welcome

[@nanisurya7550]

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?

[@techdose4u]

Geeksforgeeks

[@nanisurya7550]

@@techdose4u thank you sir

[@techdose4u]

Welcome :)

[@revarevanth1800]

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

[@gugli28]

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?

[@shivambaghel9668]

What will be the time complexity of 1D solution

[@shresthmishra9329]

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.

[@techdose4u]

You should try taking a 1D vector and use the same equation for the same vector. Think. You will get it.

[@shresthmishra9329]

@@techdose4u ok sir

[@bharatkumar-be9ki]

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.

[@aakashgoswami2356]

Sir what is the intuition for O(n) sc.... I mean why this algo work?

[@danghuynguyen8579]

I have a question for this problem, what if the order matter. Ex: 5 = 2 + 2 + 1 = 1 + 2 + 2 = 2 + 1 + 2

[@ankitsharma-dw4rz]

Can you help me with a scenario where amount is not absolute like amount is 15.05.

[@asktostranger8296]

In which company you are in And what are your classification Sorry for the personal question But i want to know, 🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@techdose4u]

Follow on linkedIn

[@asktostranger8296]

@@techdose4u by which name you are in linked in

[@mahesh4274]

@@asktostranger8296 Go to channels about tab.

[@simplecop123]

He is working at Samsung R n D

[@HimanshuSingh-ob9qo]

👍

[@techdose4u]

👍

[@omparikh4426]

please also make coin change 1

[@techdose4u]

Yes I surely will in future

[@fatimajaffal9843]

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

[@tacklewithtricksbykajala.4231]

But what if the amount is large

[@shresthmishra9329]

Sir :) 🙏

[@techdose4u]

:)

[@rahulbhati3079]

sir can we do in o(n) space complexity

[@techdose4u]

Yes correct because you need to maitain just the previous state and update elements from beginning to end.

[@rahulbhati3079]

@@techdose4u i didn' tget sir can you elaborate

[@sayandas170693]

Linear DP solution with meaningful comments. O(n) Space leetcode.com/submissions/detail/445825375/

[@mallikakejriwal3729]

what is time complexity?

[@evgeni-nabokov]

amount x number of coins.

[@aggipettiundhamama6217]

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

[@techdose4u]

👍🏼

[@abhijeetkumar2204]

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

[@vijayakumareyunni6010]

Explanation was off and not at all clear starting from 7.10 thru 13.16. Hence, didn't watch after that.

[@manngondaliya4704]

What to do if 1 1 1 1 2 and 2 1 1 1 1 are both allowed in answer?

[@ShamilShafi]

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]

[@techdose4u]

Change the condition. Tweak some points in the code and you will manage to do it. Try to tweak and test your code.

[@md_aaqil8027]

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

[@anshshah4927]

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?

[@techdose4u]

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.

[@ryanaugustine5940]

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; }

[@bharatkumar-be9ki]

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.