DP 22. Coin Change 2 | Infinite Supply Problems | DP on Subsequences
ฝัง
- เผยแพร่เมื่อ 14 ต.ค. 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...
![[UNCUT]“ฅนตื่นธรรม”ปะทะ“หมอปลา-ปู่มหามุนี-อั๋นโอกิ”สะเทือนกระทรวงเวทมนตร์ Iคนดังนั่งเคลียร์I10 ตค.67](http://i.ytimg.com/vi/peMD_SAkwNc/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
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.
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 ✅
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 question on my own even before watching this video. Thank you so much for this wonderful playlist.
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 👏👏
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 problem without watching the solution. thanks a lot striver for teaching such tough topic for beginners in such easy way.
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)
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
Its still hard to believe i can literally code on my own now after watching your series , never thought dp would be this easy !
understood ! memoization, tabulation , space optimization all done without watching video
was Able to think of complete solution the moment you explained question.Big Thanks
UNDERSTOOD sir...
Thanku so much for this amazing series.
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;
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 🔥🔥🔥
UNDERSTOOD.......Thank You So Much for this wonderful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Undetsood !! Solved by myself and then watched the video . Thanks Striver.
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, great content as always by Striver! ❤
Even though you are busy, you uploaded video for us. Great.!!
Understood striver bhaiya ✌ -- solve this problem before watching this video 💪💪
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
Following the entire series and was able to do this question on my own without watching the video! Thankyou so much :)
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
we can write one more base case if(target == 0) return 1;
along with target < 0 || i == -1 return 0 will work fine
LOL, you are destroying all the jobs and platforms of paid content creators 😁😁
Thanks for the video !!
Thanks a lot @Raj Bhaiya for reducing the fear of Dp.
Now I can think of the intuition by my own.
Thank you so much for your DSA playlist, my FAANG interviews are going butter smooth xD
solved the problem before watching the video..✌✌
Understood ❤
understood saar! amazing teacher you aareee!!!!
Could solve this one on my own!
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]
you are the real gem....thanks man
Solved by my own !! yeeeeehhh
@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 did all on my own
Understood!
This is best dp series ever ...🔥🔥🔥
base case can be generalized if we go with array size rather than array index.
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.
understand sir thankyou so much for this amazing content its priceless
Why not adding a plus one here too in the take case?
Can we add a base case where
If(target==0)return 1;
Thankyou so much Striver
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
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.
I solved this problem on my own with all methods, from the knowledge of previous videos.
Thanks Striver
watched the first 2 mins, and solved it myself.. Thanks bhaiya for training us so so well
Understood Perfectly 🎆🔥🔥🔥
Ek doubt hai base case me mod operator true and false return krega na
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
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
Undestood...
Just wanted to ask why haven't you mentioned that single array space optimised solution over here? Like in my opinion, we can just use a prev array and traverse target from 0 to target and keep updating the prev array only. Since in the notTake case, we are taking the current idx state only and in the take case we are taking the pre calculated value.
Correct me if I am wrong striver.
for(int i=1; i
one of the best solution i have ever seen on youtube . thank you striver bhaiya
i need to understand why target == 0 is not in base case
int solve(int index, int target, vector &coins, vector &memo){
if(target == 0)
return 1;
if(index == 0){
if(target%coins[index] == 0)
return 1;
return 0;
}
if(memo[index][target] != -1)
return memo[index][target];
int not_take = solve(index-1, target, coins, memo);
int take = 0;
if(coins[index]
Yes same bro I also have this question
moreover the base condition in the program of the video is returning boolean.
I tried both the approaches for base cases where ind == 0 and also if target == 0: retrun 1
Both of the bases cases still clear the submission check and are accepted.
we can use both the base cases or just the base case with ind==0, both are accepted.
I solved this problem on my own. Thanks striver. You teach amazing.
"Solve this problem with my own without seeing the video my confidence and thinking skill are growing day by day thank you Striver"
Understood Thank you so much.
just loving this series,getting lots of confidence
now i am solving own and seeing videos to verify my approach ... thanks strive ... UNDERSTOOD
Thank You and Understood ❤.
you make me imagine recursion without writing it down.. GOAT❤
Why didn't we add 1 in the take case?
Understood...Completed (22/56)
Thank you so much!
Understood all the four methods 1) Recursion, 2) Memoization, 3) Tabulation, 4) Space Optimization
Able to solve using the concept of prev coin change 1 problem. Thanks
In this can we add a base case if T==0 return 1
Yeah I think we should, if there is a possibility of reaching T=0 at any index prior to ind=0 it should also be considered.
Please upload notes for this and previous video . They are icing on the cake.
understood
uderstood ! easy to understand the way of your explanation.
in the base cases why you didnt considered the T you only thought about indexes
UNDERSTOOD
Understood!!!Thank you for inflicting such confidence
thnx i did this on my own
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)
UNDERSTOOD... !
Thanks striver for the video... :)
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.
Understood sir.
Dont we have to re initialize cur at the begining of the outer loop ?
21:36
Great Stuff.
in the base case is T is divisible by arr[0] then we should return T/arr[0 na not 1??
|
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;
Understood
Understood!
Using single array solution -
long countWaysToMakeChange(int* deno, int n, int tar)
{
vector prev(tar+1);
for(int j=0 ; j
why we didnt consider the base case case where target ==0 ?
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
recursive, memoization sab likh liya vo bhi khud se aur chal bhi gaya leetcode pe. par jab tabulation likha toh galti se pick ko do baar init karne ki vajah se nahi hua. fir bohot der baad chatGPT ko diya code toh vo bhol gadhe do baar int pick likha hua hai. chalo koi nahi ab ye error bhi yaad rahega.
note: this note is for future me
Understood 😊
for target = 0 what will be the base case??
will it return 0???
done Recursion , memoization, tabulation , space optimisation without watching video
Understood and did all the code by myself !