DP 22. Coin Change 2 | Infinite Supply Problems | DP on Subsequences
Вставка
- Опубліковано 21 гру 2024
- Lecture Notes/C++/Java Codes: takeuforward.o...
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/take...
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.o...
You can also get in touch with me at my social handles: linktr.ee/take...
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
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?
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!
I tried this on my own and I was super happy to solve this problem with all the methods. Thanks, Brother ❤
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 think the consequence of this DP series will be free education and no college😃
3 months ago I gave up on dp after watching 20 videos, but now I solved this problem on my own from bruth forces to space optimisation ❤❤🔥 you are legend brooo
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 ✅
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
I was able to do this question on my own even before watching this video. Thank you so much for this wonderful playlist.
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
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 👏👏
Undetsood !! Solved by myself and then watched the video . Thanks Striver.
Solved this problem on my own by using concepts of DP-18 Coin Change - 1.
Still understood all : - Recursion, Memoization, Tabulation & Space Optimization
#Understood #Hatsoff #Striver
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.
UNDERSTOOD.......Thank You So Much for this wonderful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
UNDERSTOOD sir...
Thanku so much for this amazing series.
understood ! memoization, tabulation , space optimization all done without watching video
Its still hard to believe i can literally code on my own now after watching your series , never thought dp would be this easy !
Even though you are busy, you uploaded video for us. Great.!!
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
Great video! But we dont actually need 2 vectors prev and curr. Only one is enough. This is my approach:
long countWaysToMakeChange(int *d, int n, int value)
{
vectordp(value+1,1);
int i,j;
for(i=1;i
Following the entire series and was able to do this question on my own without watching the video! Thankyou so much :)
Understood, great content as always by Striver! ❤
was Able to think of complete solution the moment you explained question.Big Thanks
Understood striver bhaiya ✌ -- solve this problem before watching this video 💪💪
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;
Thanks a lot @Raj Bhaiya for reducing the fear of Dp.
Now I can think of the intuition by my own.
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 🔥🔥🔥
LOL, you are destroying all the jobs and platforms of paid content creators 😁😁
Thanks for the video !!
Thank you so much for your DSA playlist, my FAANG interviews are going butter smooth xD
you are the real gem....thanks man
This is best dp series ever ...🔥🔥🔥
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)
Understood ❤
solved the problem before watching the video..✌✌
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)) ; " ?
Solved by my own !! yeeeeehhh
Understood Perfectly 🎆🔥🔥🔥
Ek doubt hai base case me mod operator true and false return krega na
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
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
Dont we have to re initialize cur at the begining of the outer loop ?
21:36
Can we add a base case where
If(target==0)return 1;
understood saar! amazing teacher you aareee!!!!
watched the first 2 mins, and solved it myself.. Thanks bhaiya for training us so so well
Thankyou so much Striver
understand sir thankyou so much for this amazing content its priceless
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.
Could solve this one on my own!
Thank You and Understood ❤.
I solved this problem on my own. Thanks striver. You teach amazing.
UNDERSTOOD THNX STRIVERRR
"Solve this problem with my own without seeing the video my confidence and thinking skill are growing day by day thank you Striver"
one of the best solution i have ever seen on youtube . thank you striver bhaiya
just loving this series,getting lots of confidence
Understood Thank you so much.
why do we write separate condition for index ==0 ?
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.
@takeUforward @everyone Can someone explains what the difference between the problem statement of DP 20 and 22? Because i think both the problem are same.
here we are counting the total number of ways.....in dp 20 we are counting the minimum number of coins the code is similar only just the return values are different
UNDERSTOOD !!!
Why not adding a plus one here too in the take case?
you make me imagine recursion without writing it down.. GOAT❤
Understood!!!Thank you for inflicting such confidence
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
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 🙏 !!
understood did all on my own
UNDERSTOOD... !
Thanks striver for the video... :)
Should we include a base condition of target==0 and then return 1,
i have the same doubt i included it and it worked for me
we can write one more base case if(target == 0) return 1;
along with target < 0 || i == -1 return 0 will work fine
I have a doubt . upon entering a test case [1, 2 , 5] and amount 0, i am getting the expected output in leetocode as 1. How is this possible? Is not taking any coin also counted as a combination?
in the strivers code he didn't assume the case amount == 0 condition . In leetcode we have to consider the case when amount == 0 and return 1;
now i am solving own and seeing videos to verify my approach ... thanks strive ... UNDERSTOOD
I have one doubt, how can we return boolean from a function which returns long?
prev and curr array are also long type in first for loop wherever condition satisfies ,prev will store value 1(as in true==1 & false =0)
base case can be generalized if we go with array size rather than array index.
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]
Recursion pseudocode: 10:30
How to know if we have to take *f(denominations, n-1,value);* n or n-1
Why didn't we add 1 in the take case?
Thank you so much!
Understood 😊
Striver Bhaiya again i think we can also optimize it in terms of space by using just an single array
Yes will teach in next video.
why we didnt consider the base case case where target ==0 ?
Understood brother..
solved before seeing the video..
It's only because of u striver..🔥🔥
Understood!
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
Why are we not adding +1 when we pick the coin?
uderstood ! easy to understand the way of your explanation.
Sir what is int *a how is that a array
finally after 21 videos i was able to solve question using memoization as well as tabulation without any help.
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
int tk = 0;
if(target>=coins[ind]){
int tk = minCoins(ind-1, target - coins[ind], dp, coins);
}
we are using the case where only and only if the target is greater than the current coin in the array then the take part will work otherwise it will simply not run the will take recursion
Great Stuff.
yes i understood
I think one more base case needed
If (target==0)
Return 1;
Even though it can be achieved by
Function of not take but this base case can be added
Please correct me if I am wrong
Understood sir.
in the base case is T is divisible by arr[0] then we should return T/arr[0 na not 1??
|
Understood all the four methods 1) Recursion, 2) Memoization, 3) Tabulation, 4) Space Optimization
Understood!
Using single array solution -
long countWaysToMakeChange(int* deno, int n, int tar)
{
vector prev(tar+1);
for(int j=0 ; j
I think I am become addicted to yours dp video 😳🤯
thnx i did this on my own