DP 22. Coin Change 2 | Infinite Supply Problems | DP on Subsequences
HTML-код
- Опубликовано: 15 фев 2022
- Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/33Kd8o2
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the problem of ways to form Coin Change. We start with memoization, then tabulation, then two-row space optimization. This problem is the eighth problem on DP on Subsequences Pattern. Please watch DP 14 before watching this.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward
![CENTRAL CEE - GEN Z LUV [VERTICAL VIDEO]](http://i.ytimg.com/vi/VIbidJm9q34/mqdefault.jpg)
This problem can also be solved using 1D array, we have discussed about it in DP 23.
int change(int amount, vector& coins) {
vector dp(amount+1, 0);
dp[0]=1;
for(int &coin: coins) {
for(int i=coin; i
Can't we add the case when value==0
And fill the first column of dp array with 1
undderstood
Understood! Since you've already explained these concepts so well in the previous problem, I was able to solve it on my own. Thanks, Striver! 💯
Have been following your dp series and was able to solve the problem by my own successfully in a single try, thanks a lot for the efforts you took to provide such a great dp series
I tried this on my own and I was super happy to solve this problem with all the methods. Thanks, Brother ❤
I think the consequence of this DP series will be free education and no college😃
ths was very same to coin Change 1, just instead of returning minimum, we need to return 1 if path exists or 0 if does not
That's what I'm thinking about 🤔
Yes, you're right.
I was able to do this question on my own even before watching this video. Thank you so much for this wonderful playlist.
Thank you so much for your DSA playlist, my FAANG interviews are going butter smooth xD
was Able to think of complete solution the moment you explained question.Big Thanks
Was able to think of the solution even before he started explaining the recursive approach... Thanks to striver... Kudos to your effort...
same
land
i have a doubt, why didnt he take a base case with target == 0
@@abhilash4976 bro it is considered at time you reach index 0
@@abhilash4976 did you found out why?
Following the entire series and was able to do this question on my own without watching the video! Thankyou so much :)
UNDERSTOOD sir...
Thanku so much for this amazing series.
Hi everyone. Thanks a lot Striver for making DP so easy and interesting for all of us. Just had one small query (might sound trivial 😅)- In this problem, amount and ind are changing params and according to recursion, we have to write the base cases for all the changing parameters. Why don't we handle the case of amount==0? As if amount==0, we can return 1 as we have achived 1 subsequence equal to the amount.
Thanks in advance.
yeah bro, we need to take amount == 0 case as well. Leetcode throws an error if u dont take this case. Thanks for pointing it out!
understood ! memoization, tabulation , space optimization all done without watching video
UNDERSTOOD.......Thank You So Much for this wonderful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Striver, may I suggest next videos? Word Break I & II. These problems have both recursive and DP solutions I think they would make excellent videos. Thanks
I was able to do this problem without watching the solution. thanks a lot striver for teaching such tough topic for beginners in such easy way.
you are the real gem....thanks man
I am able to solve coin change 2,Unbounded Knapsack and Rod cutting problem with memoization ,tabulation and space optimization on my own without watching video. Thanks a lot Striver!! Surely the Best DP playlist 🔥🔥🔥
Was able to successfully write both top-down and bottom-up code at once without even starting the video...Thanks striver for bringing me till this point...the journey will continue ✅
Understood!!!Thank you for inflicting such confidence
understood saar! amazing teacher you aareee!!!!
Understood striver bhaiya ✌ -- solve this problem before watching this video 💪💪
Understood Thank you so much.
Just a humble request please please please don't stop making the videos after you would have left India ... Now can confidently solve any dp problem with all four approaches taught by u ... Simply amazing teaching by u bhaiya 👏👏
Its still hard to believe i can literally code on my own now after watching your series , never thought dp would be this easy !
Thankyou so much Striver
I solved this problem on my own. Thanks striver. You teach amazing.
understand sir thankyou so much for this amazing content its priceless
came to know about this channel from my brother
he is also doing CSE from jalpaiguri government collage... he also told u have done ur engineering from the same collage
thank u very much sir
solved the problem before watching the video..✌✌
watched the first 2 mins, and solved it myself.. Thanks bhaiya for training us so so well
I solved this problem on my own with all methods, from the knowledge of previous videos.
Thanks Striver
Thank You and Understood ❤.
Even though you are busy, you uploaded video for us. Great.!!
base case can be generalized if we go with array size rather than array index.
just loving this series,getting lots of confidence
Thank you so much!
"Understood" and thank you!
I am able to think of the solution before you start explaining the recursive approach .Thank you striver..without you it can't be possible.i owe you a big one.
Great Stuff.
Understood Perfectly 🎆🔥🔥🔥
Ek doubt hai base case me mod operator true and false return krega na
understood did all on my own
LOL, you are destroying all the jobs and platforms of paid content creators 😁😁
Thanks for the video !!
UNDERSTOOD... !
Thanks striver for the video... :)
Thanks a lot @Raj Bhaiya for reducing the fear of Dp.
Now I can think of the intuition by my own.
Understood ❤
Could solve this one on my own!
Solved by my own !! yeeeeehhh
If anyone didn't understand
if(n==0) return k%arr[0]==0;
Well, it means whether constantly decreasing the number by arr[0] will lead k to 0
Or in place of this, you can write
if(n==-1) return k==0;
one of the best solution i have ever seen on youtube . thank you striver bhaiya
Understood!
now i am solving own and seeing videos to verify my approach ... thanks strive ... UNDERSTOOD
Understood 😊
Thank you so much bhaiya for all the knowledge you are sharing with us.
thnx i did this on my own
Understood🎉
Understood sir.
understood!!
Understood!!
understood :)❤
This is best dp series ever ...🔥🔥🔥
Please upload notes for this and previous video . They are icing on the cake.
Was able to solve it without looking at the video....thank you striver😁
Understood, thanks
Again, Similar to the previous time (DP 20) when we have to stay at same index in case of selection.
In this scenario if we go for tabulation in reverse fashion, then it gives 1 in case of correct answer but gives correct answer in case of moving forward from 0.
Could you please explain why does that happens or provide a thread which might help in understanding how to go about this
Its because when we are at same index (i.e. in case we take the element), we want to use previous indexes of array. for if you want to find dp[index][target]. you need dp[index][target-arr[index]], you want some value in same row but before current index.
Now if you fill from reverse you haven't filled previous indexes and they are still zero, so you need to fill from starting.
Understood :)
guys , this concept are tough . if we not able to solve in one go ...relax even he is summiting multiple times ....hatsoff to the effort by the striver , he is helping alot .
Striver bhaiya pdaye toh sab aasan hai..
Wese amit tu electrical engineering kar rkha hai kisi jhatu college se..esliye tu jhatu hi hai
Striver has submitted in its first attempt
@@pratik.784Bhai wo candidate master h , he has a lot of experience
Why do we take value + 1 here, whereas in some another video we took value only ? *vector dp(n,vector (value+1,-1))*
because the values of the value variable range from 0 to value (both included)
How do it if we have to count Unordered ways instead of ordered ways?
For example: {1,2,1} and {2,1,1} will be considered Different.
You can Refer to Cses Coin combinations 1 for this problem.
Yes, I checked that
uderstood ! easy to understand the way of your explanation.
finally after 21 videos i was able to solve question using memoization as well as tabulation without any help.
Striver, in memoization approach, do we need to write this case if(value == 0) return 0 ; otherwise, the value will go negative very soon. The answer is correct both ways, but I think adding this to our code will make it much more efficient. I have pasted the memoization approach below:
#include
long long int helper(int* denominations , int index , int value , vector& dp){
if(value < 0)
return 0 ;
if(value == 0)
return 1 ;
if(index == 0){
if(value % denominations[index] == 0) return 1 ;
else return 0 ;
}
if(dp[index][value] != -1)
return dp[index][value] ;
long long int notTake = helper(denominations , index - 1 , value , dp) ;
long long int take = 0 ;
if(denominations[index]
why are we using value+1 in "vector dp(n , vector(value+1 , -1)) ; " ?
UNDERSTOOD
Understood Sir. Hats off to you for what you are doing.
Try running the tabulation for :
Tar = 9 and coins = {5,6,7,9,11,12,13,15}
It fails !!
Because , what I think is , we have missed the initialisation wherein the Tar = 0 can be achieved at all indices . So I added this line of code above the tabulation :
for(int j=0; j>=n ; j++)
dp[j][0] = 1 ;
But , when I add this, all other test cases fail , so plz help me if anyone can 🙏 !!
understoood
can someone explain me base case in tabular? how to do that and what it does
understood
Understood and did all the code by myself !
How to know if we have to take *f(denominations, n-1,value);* n or n-1
Able to solve using the concept of prev coin change 1 problem. Thanks
we can write one more base case if(target == 0) return 1;
UNDERSTOOD! and going forward everyday!
you make me imagine recursion without writing it down.. GOAT❤
If we consider the recursive part of the function where we dont decrease the index , in that case hw will my function reach the base case of index =0 since only amt will decrease and index will remain same hence may result in runtime error right? I dont understand hw that part is working
could u please explain how did u take the base ase of (if (ind==0)) didnt really get that part
cuz int he Take case we will never reach ind==0 so the recussion will keep continuing so cud u please explain that part
Understood
I have 3 questions:
1) If we are counting total number of ways, would optimal substructure be applied?
2) Is this the same problem statement as Leetcode's Combination Sum 1 and 2. If it is, there I didn't use dp, and they didn't ask to optimize.
3) Instead of write that base case with two if statements, can we just write if(target < 0 || index
"Solve this problem with my own without seeing the video my confidence and thinking skill are growing day by day thank you Striver"
Why is there no base case where if (t==0) return 1; ?
small change is needed in tabulated solution for cases like target = 7 and array [3,7] where it'll fail . Amazing playlist btw:
n = len(coins)
dp = [[0 for _ in range(amount+1)] for _ in range(n+1)]
#1 way to select 0 amount
for j in range(n):
dp[j][0] = 1
for index in range(n-1,-1,-1):
for remAmount in range(1,amount+1):
res = dp[index+1][remAmount]
if remAmount - coins[index] >= 0:
res += dp[index][remAmount-coins[index]]
dp[index][remAmount] = res
return dp[0][amount]
I think I am become addicted to yours dp video 😳🤯
why are we using value+1 in "vector dp(n , vector(value+1 , -1)) ; " ?
making the 2d array ...see some of the pepcoding tabulation dp videos you will understand
Why not adding a plus one here too in the take case?
Understood brother..
solved before seeing the video..
It's only because of u striver..🔥🔥
Understood, sir. Thank you very much.
@take_U_forward , i am not able to understand tabulation till now , I have watched all last 21 videos but still finding difficult to do tabulation
why we didnt consider the base case case where target ==0 ?
Understood!
Using single array solution -
long countWaysToMakeChange(int* deno, int n, int tar)
{
vector prev(tar+1);
for(int j=0 ; j
Thanks for DP playlist