DP 20. Minimum Coins | DP on Subsequences | Infinite Supplies Pattern
ฝัง
- เผยแพร่เมื่อ 5 ต.ค. 2024
- Lecture Notes/C++/Java Codes: takeuforward.o...
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/take...
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.o...
You can also get in touch with me at my social handles: linktr.ee/take...
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
*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
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 💡
Now this DP SERIES is going as per expectations.
As always
UNDERSTOOD 🔥 😊
indeed
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
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
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 🙇
We can solve it using only one array :
vectorprev(x+1,0);
for(int i=0;i
unlike in previous question for single array optimization, why didn't we changed inner loop from --> for(int j=x; j>=0; j--) ?
@@spiral546 Let me explain the key distinction:
0/1 Knapsack Problem:
In the 0/1 Knapsack problem, you can either include an item or exclude it, but you can't include an item multiple times. Each item can only be chosen once. That’s why we loop backward in the knapsack problem, to avoid overwriting values that still need to be used in the current iteration.
For example, let's say we're considering adding an item that weighs w:
If you loop forward, you might accidentally update the result for a smaller weight using the current item (which you shouldn't).
But if you loop backward, you safely update the values for higher weights first, leaving the smaller weights unchanged until they are processed in the next iteration.
So, in the 0/1 knapsack, backward looping ensures that each item is only used once.
Coin Change Problem:
In the Coin Change problem, the difference is that each coin can be used multiple times. Therefore, for each coin, you want to use the result of smaller amounts that include previous uses of the same coin.
If you loop backward, you might use a value that has already been updated in the current iteration, which can lead to using the same coin more than once in an incorrect way.
Summary of Differences:
0/1 Knapsack: Each item can only be used once, so you loop backward to ensure that earlier values (smaller weights) aren't affected by current updates.
Coin Change: Each coin can be used multiple times, so you need to loop forward to ensure that you're using values from the previous iteration and not overwriting them prematurely.
There is no any Substitute of Your content on TH-cam.
U r great ❤️
Facing DP problems: No fear... Striver is here...🤩 thankyou bro.
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
Wow i solved this problem today morning same way striver taught the previous topics!! You are rocking man
Congrats buddy!!!!
Thank you for existing striver ! Helping others is the best thing any human can ever do! U are the best of our kind.
done this before 3 month after 3 month i Tried this question and boom got this easily u teach very well 👊👊
Getting better at DP day by day Thankyou Striver!!!
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
I love watching these 30 min videos that spend 40 minutes making notes !
@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.
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.
UNDERSTOOD.............Thank You So Much Striver Bhaiya for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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]
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...
1D optimisation is great , loved it 👍
Understood to the Highest Level !!!!!!! Thank You Sir.
why we are not considering the base case of when target become zero?
this question blew my mind
Understood!! This DP series is magical! 💫🧿
similar to combination sum in your recursion playlist so this was easy for me !Us
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)
this felt good to watch, thank you :)
understood, i was able to write the recurrence solution without watching the vedio, thankyou striver
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
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
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.
Greatly explained
Totally understood the concept, you made it easy for us! Thanks for all your efforts.
Thanks for explaining with so much clarity. Able to do all recursion, memoization, tabulation and finally space optimization :)
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.
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
very much similar to combination sums that u taught..#striver takes us forward
Thanks Striver
One query,
In tabulation if we go the other way round (In backward direction):
Putting the snippet here:
/* Here, x is our required sum and n is the size of array containing available coins*/
for(int i = 0; i = 0; ind--)
{
for(int target = x; target >= 0; target--)
{
// Not pick
int nPick = dp[ind+1][target];
// Pick current
int pick = 1e9;
if(num[ind] = 1e9)
return -1;
return dp[0][x];
/*
Here, in this case I am getting correct answer for -1 cases but for all the other cases instead of getting the correct value, I am getting 1
If I modify the logic to move from 0 to end in that case the code is working.
Could you please explain or give a thread so that I can understand what exactly is the issue here.
*/
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
Thanks a lot Striver, another question I was able to solve without seeing video just because of your old videos
for(int i=0; i
Single row optimisation is the best..
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
It is giving TLE in both memoization and tabulation
His way of teaching never discriminates with a backbencher
Sir I think writing the base case when target hits 0 would be some more optimal
Thanks Striver!
if( x == 0) return 0;
if(i==-1)return 1e8;
This two base case will handle all.
If(target==0) ko kaise handle karenge?
@@krishanpratap3286 target hi to X hai...if target == 0 we will just return 0
leetcode accept nahi kar raha
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
@striver thanks again for great video, just adding more point for the people
- here we can not reduce to futher 1 row since both curr and prev row are needed
- in knapsack prob we only needed values from prev row so it was feasible but here values from both row are needed so for problems with multiple use space optimization to only 2 row is possible
int f(int target, vector &num, vector &dp){
if(target==0){
return 0;
}
int ans=1e8;
if(dp[target]!=-1) return dp[target];
for(auto ele:num){
if(ele
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 it clearly. Thank you so much.
I thought that I can replace 1e9 with Integer.MAX_VALUE, but that led to wrong ans, since we are adding 1 to it in one of recursive calls, and Integer.MAX_VALUE + 1 = Integer.MIN_VALUE, which led to wrong ans.
I am curious - how and why does only 1e9 work? Can it be 1e8 OR 1e10?
You can use INT_MAX, but do 1 + fn() only if result of fn() is not INT_MAX
What's wrong with this?
public static int minimumElements(int num[], int x) {
return (int)minimumElements(num, x, num.length-1);
}
public static long minimumElements(int num[], int target, int i) {
if(i == 0) {
if(target % num[0] == 0) return target / num[0];
return Integer.MAX_VALUE;
}
long take = Integer.MAX_VALUE;
if(num[i] >= target)
take = 1 + minimumElements(num, target - num[i], i);
long drop = minimumElements(num, target, i-1);
return Math.min(take, drop);
}
I solved first dp question by myself ..ty striver ❤️❤️❤️❤️
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...
shouldn't we also check for target being 0 in the recurrence relation for when the target has become zero but we haven't reached the index 0?
no need it will be covered as part of the case where we just not pick any thing till index 0 after the target became 0.
Delhi Public School?
It can be easily space optimised with only using 1 vector row like we did in knapsack
Understood Thank you so much.
Same as Combination Sum ? 🤔
Understood ❤
i think ur god.....u came here on earth for us!!!
Thank you!!! Was waiting for this eagerly.
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 striver😇
UNDERSTOOD ❤
Understood! Thank you for your detailed explanation as always !!
Understood. Thankyou sir
UNDERSTOOD... !
Thanks striver for the video... :)
Thanks soooooooooooooo much Striver!
Understood, sir. Thank you very much.
Understood and really thankful for your great efforts.
For me , it is the best yt channel , for coding related stuff❤
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?
why can't we add the number of the coins picked up like this:
pick = solve(coins, amount % coins[index], index-1, dp) + amount/coins[index];
understood
understood...u r messiah in human form...best dsa content on youTube for sure.
Thank you so much!
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??
understood// but doubt why tabulation fail while memoization passed because in the last part of space optimization we again using the tabulation which is passed but we know time complexity is same in both the cases.
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.
Explanation is mind-blowing but don't edit video while writing code as I see in writing recursion code you where written max(take,nottake) but when you submit it was min so you edited video.
Thank you
If we apply greedy in gfg question minimum no of coins it passes all test cases even in editorial they have mentioned greedy solution is working, may be because of denominations given in question the greedy might work. But if there is no uniformity why is greedy working?
[2,5,10,1]
Target= 27
Why the code gives wrong output for this
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.
Hi Striver, why greedy works when we did same problem with Indian Currency ?
I had one question about this vs knapsack. Usually, when we want min/max of something, if the base case does not satisfy the condition we return max/min as we do in this problem. But in knapsack we returned a 0 instead of a min value. I don't understand when to return min/max vs 0. Any help would be appreciated.
Hey, did you find the explanation to this?
one is about the path and other is about value
Clean and clear explanation ☺️☺️.
Understood 👍🏼👍🏼
This problem could be done with the help of 1d dp also, 😀, but got to learn another approach how 2d dp works here
Better than 98.7% on Code Studio | 1D DP one loop
#include
int minimumElements(vector &coins, int amount)
{
if(amount == 0) return 0;
vector dp(amount+1,-1);
dp[0] = 0;
for(int i=1; i=0) ans = min(ans, 1 + dp[i-a]);
}
dp[i] = ans;
}
return dp[amount]>=1e8 ? -1 : dp[amount];
}
understood bro
Understood sir!
Understooood 🔥🔥🔥🔥🔥
thx striver for this wonderful series.
Awesome.....Loved it