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.
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 🙇
@@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.
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 :)
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 💡
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.
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.
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...
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.
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
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.
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]
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)
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 :)🙏
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??
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
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
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.
@@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.
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.
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?
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.
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
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
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.
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. */
@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.
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.
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.
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.
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?
Striver i dont know whether you will see this, but your videos and SDE sheet have changed my life. I got selected as an intern today in a product company only thanks to you my friend. Love you striver bhaii!!!!!!!!!! You're the best ever youtuber i know
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.
hey striver. i solved this question by same logic and solution got accepted on leetcode but it gave TLE and Run time error on CSES problem sheet. if you can look into this then it would be a great help for me. i didn't get the logic of other solns. And i do cp that's why i solved those problems.
We can also do this using one parameter(amount) in recursion:- // Recursion Memoization Code for reference class Solution { private: int f(vector &coins, int amount, vector &dp) { if(amount == 0) return 0; if(amount < 0) return -10000000; if(dp[amount] != -1) return dp[amount]; int ans = 1000000; for(int i=0; i
Doubt: i tried the same technique but instead of taking "take" as 1 + helper() i kept count as a variable within the helper function and returned min(take, ntake). also, when amount==0 then i returned count instead of 0, accordingly i made all the changes. it worked for some cases not for others. can anyone explain why this happened?
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
Facing DP problems: No fear... Striver is here...🤩 thankyou bro.
*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
Now this DP SERIES is going as per expectations.
As always
UNDERSTOOD 🔥 😊
indeed
There is no any Substitute of Your content on UA-cam.
U r great ❤️
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.
j loop should be reverse order
@@deekshithavarma3997 refer to @mohaknigam solution
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
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 💡
wow
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
I love watching these 30 min videos that spend 40 minutes making notes !
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!!!
UNDERSTOOD.............Thank You So Much Striver Bhaiya for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Understood to the Highest Level !!!!!!! Thank You Sir.
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
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!! This DP series is magical! 💫🧿
Wow i solved this problem today morning same way striver taught the previous topics!! You are rocking man
Congrats buddy!!!!
#Understood #DP20 #Hatsoff #Striver
Did this question on my own post the step of "STAYING AT SAME INDEX". Man this series is literally 🔥 🔥
F(n-1)
understood...u r messiah in human form...best dsa content on youTube for sure.
this felt good to watch, thank you :)
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!
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, i was able to write the recurrence solution without watching the vedio, thankyou striver
Totally understood the concept, you made it easy for us! Thanks for all your efforts.
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
Thanks Striver
similar to combination sum in your recursion playlist so this was easy for me !Us
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]
Thanks for explaining with so much clarity. Able to do all recursion, memoization, tabulation and finally space optimization :)
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)
why we are not considering the base case of when target become zero?
this question blew my mind
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 :)🙏
*Complexities*
Recursion: 21:20
Memoization: 23:00
His way of teaching never discriminates with a backbencher
Thanks!
For me , it is the best yt channel , for coding related stuff❤
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??
very much similar to combination sums that u taught..#striver takes us forward
I solved first dp question by myself ..ty striver ❤️❤️❤️❤️
Clean and clear explanation ☺️☺️.
Understood 👍🏼👍🏼
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
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 for your detailed explanation as always !!
i think ur god.....u came here on earth for us!!!
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...
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...Completed (20/56)
Greatly explained
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... !
Thanks striver for the video... :)
Thanks a lot Striver, another question I was able to solve without seeing video just because of your old videos
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.
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 Bro :) One Row solution is awesome :)
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 ❤
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?
Understooood 🔥🔥🔥🔥🔥
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
for(int i=0; i
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 man! Amazing work! Keep up the good work
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);
}
Thank you!!! Was waiting for this eagerly.
UNDERSTOOD 🔥 😊
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.
*/
Yesssss!!!. Did it on my own. Understood Sir ✅
UNDERSTOOD ❤
Thanks soooooooooooooo much Striver!
Understood it clearly. Thank you so much.
I solved this question on my own !!!😁
@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.
No
could solve it on my own, thanks!
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.
Amazing!! Just tired of scrolling Leetcode discuss, here is the best answer, Thanks!!❤🔥 🙌 💥
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
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.
Thanks Striver!
Understood, sir. Thank you very much.
Understood Thank you so much.
Understood. Thankyou sir
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?
Understood and really thankful for your great efforts.
You r the best teacher brother🔥
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];
Striver i dont know whether you will see this, but your videos and SDE sheet have changed my life. I got selected as an intern today in a product company only thanks to you my friend. Love you striver bhaii!!!!!!!!!! You're the best ever youtuber i know
Kaha lagi bro intern
@@HARSHGUPTA-lj5bizomato as delivrry boy
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.
hey striver. i solved this question by same logic and solution got accepted on leetcode but it gave TLE and Run time error on CSES problem sheet.
if you can look into this then it would be a great help for me. i didn't get the logic of other solns. And i do cp that's why i solved those problems.
what is the question name on leetcode ?
Awesome.....Loved it
We can also do this using one parameter(amount) in recursion:-
// Recursion Memoization Code for reference
class Solution {
private:
int f(vector &coins, int amount, vector &dp) {
if(amount == 0) return 0;
if(amount < 0) return -10000000;
if(dp[amount] != -1) return dp[amount];
int ans = 1000000;
for(int i=0; i
am bit confused about the space complexity, in recursion and memorization , is it O(N) or O(T) , for the recursion stack
Doubt: i tried the same technique but instead of taking "take" as 1 + helper() i kept count as a variable within the helper function and returned min(take, ntake). also, when amount==0 then i returned count instead of 0, accordingly i made all the changes. it worked for some cases not for others. can anyone explain why this happened?
Thanks for this awesome video
Sir I think writing the base case when target hits 0 would be some more optimal