DP 20. Minimum Coins | DP on Subsequences | Infinite Supplies Pattern
HTML-код
- Опубликовано: 9 фев 2022
- Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/3HJTeIl
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 minimum coins. We start with memoization, then tabulation, then two-row space optimization. This problem is the seventh 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
*that 34 minutes is way more precious than my whole college day*
felt this evert time i completed any video from strive bhiya
Esesaadreeewwww
for me its my 4 years of my btech
chhod de colllege phir
@@shreyanshbansal2859 ek saal bacha ha krletaa hui
This series isn't just explaining DP. It's more than that. Initially, for every problem, I used to tabulate and spend lots of time thinking about states, and transitions. But while following these Lecs, I got to know a path to achieve the solution, Now even in interviews, this helps me as I could explain recursive approach to the interviewer, which is very intuitive. Thankyou Striver.
bro can we use knapsack approach to reduce the space complexity more?
@@GajendraSingh-lv3jw or kitni reduce karega guru 😂
@@GajendraSingh-lv3jw
public int coinChange(int[] coins, int amount) {
int dp[] = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for(int coin : coins)
{
for(int j = coin; j amount ? - 1 : dp[amount];
}
ya bro we cant directly dive to tabulation but once we write recursion then it is so easy
one more base case can be added -
if( target == 0 ) return 0; -> in the memoization
for tabulation -> we can simply start the 2nd loop from 1 to target
no need to fil for zero as by default its value will be stored as zero.
Hope it helps :)
if you dont mind, can you send the code for tabulation
@@subhashpabbineedi7136 it is not mandatory to add this base case
@@subhashpabbineedi7136 fick tabulation only memoization
the if condition will take care of this in recursion and memoization
Actually i was wondering why t=0 case has not been taken care of
We can solve it using only one array :
vectorprev(x+1,0);
for(int i=0;i
Now this DP SERIES is going as per expectations.
As always
UNDERSTOOD 🔥 😊
indeed
Thank you bro . Felt very good , was able to attempt a dp question in one of the contest today . I am happy to witness my growth by watching your dp playlist . thanks very much 🙇
Facing DP problems: No fear... Striver is here...🤩 thankyou bro.
Understood!! This DP series is magical! 💫🧿
Totally understood the concept, you made it easy for us! Thanks for all your efforts.
Interesting Fact 🌟
So DP helps to find minimum no. of change notes/coin 💵 I get when I go for shopping. But we don't see a shopkeeper applying DP just to return the change. How does it happen that the shopkeeper always returns the minimum no. of notes 💵as change?
If you observe they apply greedy approach. But how does greedy give correct answer? Its because our currency denominations (Rs 10, Rs 20, Rs 50, Rs 100.....so on)💵 are such that the greedy approach always gives the optimal answer. Quite Interesting 💡
Getting better at DP day by day Thankyou Striver!!!
There is no any Substitute of Your content on RUclips.
U r great ❤️
Thank you for existing striver ! Helping others is the best thing any human can ever do! U are the best of our kind.
Thanks for explaining with so much clarity. Able to do all recursion, memoization, tabulation and finally space optimization :)
UNDERSTOOD.............Thank You So Much Striver Bhaiya for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
One of the best decisions that I've made to learn programming is this... Watching your videos Striver...! One day maybe I'll make even better videos...
Understood to the Highest Level !!!!!!! Thank You Sir.
Thanks Striver
Understood! Thank you for your detailed explanation as always !!
done this before 3 month after 3 month i Tried this question and boom got this easily u teach very well 👊👊
this felt good to watch, thank you :)
Thanks a lot Striver, another question I was able to solve without seeing video just because of your old videos
I love watching these 30 min videos that spend 40 minutes making notes !
Time complexity can be explained like this. O(2^Max(n, amount/min(coins))
e.g [1,2,3,4] , amount = 12. amount/min(coins) = 12/1 = 12, n=4, Max of the 2=> 12. Therefore O(2^12)
Please correct me if I am wrong.
yes its correct, but we can say its exponential in nature
but here for index=0 the function would directly return target%arr[0]. for other index it complexity should be what you mentioned
Understood it clearly. Thank you so much.
Understood man! Amazing work! Keep up the good work
Last stage optimisation to use single array:
class Solution {
public:
int MX = 1e5;
int coinChange(vector& coins, int amount) {
if (amount == 0)
return 0;
vectordpo(amount+1,0); // change vector dimension: use single array. Reason: No need to maintain 2d array. Use in line replace to basically
// access same information.
for(int i = 0; i
Clean and clear explanation ☺️☺️.
Understood 👍🏼👍🏼
similar to combination sum in your recursion playlist so this was easy for me !Us
Thank you!!! Was waiting for this eagerly.
1D optimisation is great , loved it 👍
Here we can avoid that modulo calculation and just have N row where with amount 0 mark as 0 else INF..and also in 1d dp it can be reduced to one current only instead of prev and current..so this are some optimization that can be done but you're great teacher anyways..kudos to you for giving back to community
Understood and really thankful for your great efforts.
UNDERSTOOD... !
Thanks striver for the video... :)
Most tutorials teaches how to memorise the formulae to solve DP questions but with Striver you get to understand the how thing and you can solve any problem even one that you have never encountered before.
I solved first dp question by myself ..ty striver ❤️❤️❤️❤️
Understood Thank you so much.
Thanks soooooooooooooo much Striver!
3:53 greedy doesn't work because, let suppose x is a number greater than ith coin... now it is not guaranteed that if we make x using coins index < ith coin , we will be encountering the value of ith coin while approaching the x... Denomination like 1,2,5,10,20,50,100.... follow this, let suppose we want to make 59... let suppose we didn't choose 50 rupee...now if you try to make 59 using coin
Understood. Thankyou sir
understood...u r messiah in human form...best dsa content on youTube for sure.
Quick Tip 💡 : We can space optimise it using a single array like previous question. Also, we don't have to start inner loop from back this time.
Insightful.
also i mention that not only that reduces SC but TC also , because inside the first loop we don't have to copy the prev as curr which is 0(n) extra in multiplication. the Tc reduced to approx : (target+1)*(n) from (target+1+n)*(n).
the reason because of this is when we are in same level we are independent of previous array values, as they could be used but we are checking the same coin if it can fit in again. so ind-1 is not necessary and when we not take there is no need to push any value in curr thus not needing it.
yes, but why shd we go from left to right, im getting wrong ans if j frm sum to 0. I still feel it shd be frm sum to 0, coz the values are dependent on previous values like prev[j-num[i]]., getting wrong ans. explain y shd we go frm 0 to sum
did you find answer for your query?@@dsp-io9cj
Understood!
Also, we can solve the problem using just a single array (instead of two).
int minimumElements(vector &num, int tar)
{
int n = num.size();
vector prev(tar+1);
for(int j=0 ; j
Understood, sir. Thank you very much.
Can bound the time as O(2^(N+T)) where T is the total we need. Because at max each coin can be picked T times (if coin is value 1, else less times). And space O(N+T)
Awesome.....Loved it
Understood!
UNDERSTOOD 🔥 😊
Yesssss!!!. Did it on my own. Understood Sir ✅
why we are not considering the base case of when target become zero?
Understood sir!
Understooood 🔥🔥🔥🔥🔥
Understood! Thank you so much!!
Understood, awesome explanation as always.!
Understood 😊
Understood 🔥
Understood !!
Understood ❤
Wow i solved this problem today morning same way striver taught the previous topics!! You are rocking man
Congrats buddy!!!!
Understood Bro :) One Row solution is awesome :)
Understood and great explanation as always!
very much similar to combination sums that u taught..#striver takes us forward
I have a doubt, the base condition when ind==0 , when this base case is reached from function call of not take ,code is returning value/coins[ind] for not take function call, but not-take means we are not taking a single coin, so how does it work?
understood, i was able to write the recurrence solution without watching the vedio, thankyou striver
understood!!😄
UNDERSTOOD !!! 🔥🔥🔥🔥🔥🔥
As in DP19 similar this problem can also be done using only one single array ...
Here we require the curr array also as in tabulation you could see that for pick we were writing:
pick = dp[index][sum-arr[index]];
So index is not decreasing, that means we require the curr array.
pick = curr[sum-arr[index]];
In the previous question we did not require the curr array for current array(curr) to be computed.
pick = dp[index-1][sum-arr[index]]; OR pick = prev[sum-arr[index]];
Hope this helps!!!
@@MohammadKhan-ld1xt I think we can do this using 1 array as well. Hint: just see that we only need one element from the prev array and that would already be stored in the single array we will be using. Also we go from left to right.
@@vaibhavkaul2029 Yes, you're right. Thanks for this comment. You saved my time...
Understood..!
understood!
Understood sir .
Understood.
Dear Striver,
In this problem, we are not checking the base case which occurs when the target is equal to 0 and index is not zero. This happens if ar=[1,2,3] and target = 9; then the index will stand on index 2 , recursive calling 3 times and mean while target becomes 0. So I think we have missed this case.
Am I correct or lost anywhere ? Please explain
Thank You.
See if it's stuck at index!=0 and target == 0 then it will give two calls of notpick & pick, pick will give 1e9. Notpick will give another function call, which might ultimately give 1e9 for both(pick,notpick). Check 19:30, he stopped (1,0) and if you dry run further for it you''d realise it gives 1e9 for both. Your test when run on codestudio gives the correct answer viz. 3.
Understood, thank you so much sir for such content, trust me koi ye level de he ni sakta jo aap free me de rhe hai , mujhe dp khi smajh aya to TUF pe,thank you :)🙏
Understood !!!!!
Amazing content
understood ... 👍
UNDERSTOOD
His way of teaching never discriminates with a backbencher
thx striver for this wonderful series.
thank you sir
for(int i=0; i
I now know this is obvious but you could have told us why didn't you write base case for the second state T as well, it returns 0 when T == 0 , but would have been more complete that way, thanks for the video.
man did you get the answer coz i am wondering about this as well .why its rejection does'nt cause any problem to the code
it wont affect the code as think if target becomes zero before hitting index 0 , the only recursive call of not take will run , and it wont affect the number of coins !
as there is a check before picking the coin arr[ind]
You r the best teacher brother🔥
For me , it is the best yt channel , for coding related stuff❤
NOTE FOR SELF:
When sum of smaller coins any of the larger coin then dp
@Arjun Khanna Great! could you explain the intuition behind the above conclusion!
@@maneeshguptanalluru7807 Greedy works perfectly in the case where law of uniformity is followed otherwise DP
Understood
For the recursive approach why don't we have a base case for (T==0) return 0; cuz as we can see at each stage we are either decreasing ind or target.
But the code seem to work even without (T==0) case, WHY??
better to write if(target == 0){return 0} as base case as well in order to avoid stack overflow. Also I wonder how was this working without this base case
I was thinking the same. Thanks for pointing it aloud.
when target = 0, only the notTake call is made until ind==0. For ind==0, target%x is true thus target/x is return which would be 0. So return 0 case is still working though stack space will be wasted as you pointed out.
@@anuragprasad6116 but what if target is 0 and index is not 0?
@@GirishJain if target is 0 then it will not pick anything till index 0 and hence at base case ind==0, target%x is true thus target/x is return which would be 0.
Understood!!!Thank you
Awesome Explanation Striver bhaiya.
Can we write the recursive code using the last tabular optimization approach(using prev and cur arrays)?
Can you help me with that recursive code please. I tried it but not getting AC.
Why we are declaring the curr array outside of for loop unlike the previous questions where we did it inside the first for loop?
Understood, thanks!
understood striver bro
In the space optimized code if we take it then the formula will be 1 + prev[T-nums[i]] right?
understood
I solved a question using two different recursive approaches out of which one works and other takes too much time and I am not able to figure out what is the difference can you please help?
Why are we taking cur[T - nums[ind] ] instead of prev[T - nums[ind] ] in space optimization? As per my understanding, we have been using prev row before updating the cur row in each iteration.
Hey , striver before seeing your Lecture I tried this qsn by myself and was able to came up with a recursion technique -
if(i==0)
{
if(t%num[i]!=0)
return -1;
if(t%num[i]==0)
return t/num[i];
}
if(t==0)
return 0;
if(dp[i][t]!= -2)
return dp[i][t];
int notpick= 0 + rec(i-1,t,num,dp);
int min_pick=INT_MAX;
for(int c=1;c
Bhai exactly same the technique as your then striver bhiya told this one and I feel function call stack will be same so i just search on leetcode and submit over there it will be getting submitting but acception rate less then striver bhai solution but they both are exactly same technique why this is happening
Understood Sir, thank you very much
Can we do this using 1D dp also. Like arr[]={9 6 5 1} amount =11 first in the loop we will check for 9 since it is greater than 11 now we will go for f(11-9) se similarly all others.
one doubt -> so here why can'nt we use the sorting on the coins[] array and start dividing it from the last by doing the soriting we can form the uniformity so we can use greedy isn;t it ? cause the order of the coins does'nt matter in this case