DP 20. Minimum Coins | DP on Subsequences | Infinite Supplies Pattern

[@boyidapumohit4715]

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.

[@GajendraSingh-lv3jw]

bro can we use knapsack approach to reduce the space complexity more?

[@inclinedscorpio]

@@GajendraSingh-lv3jw or kitni reduce karega guru 😂

[@krishnans1665]

@@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]; }

[@sagartaak4017]

ya bro we cant directly dive to tabulation but once we write recursion then it is so easy

[@udaypratapsingh8923]

*that 34 minutes is way more precious than my whole college day*

[@sagartaak4017]

felt this evert time i completed any video from strive bhiya

[@monstercoder3665]

Esesaadreeewwww

[@soubhikmondal8088]

for me its my 4 years of my btech

[@shreyanshbansal2859]

chhod de colllege phir

[@udaypratapsingh8923]

@@shreyanshbansal2859 ek saal bacha ha krletaa hui

[@NavaneethaKrishnan-g6x]

Facing DP problems: No fear... Striver is here...🤩 thankyou bro.

[@akr1831]

There is no any Substitute of Your content on KZbin. U r great ❤️

[@deepanshudhakate9622]

Now this DP SERIES is going as per expectations. As always UNDERSTOOD 🔥 😊

[@iamnoob7593]

indeed

[@divyambhutani6229]

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 🙇

[@CEOplays]

We can solve it using only one array : vectorprev(x+1,0); for(int i=0;i

[@spiral546]

unlike in previous question for single array optimization, why didn't we changed inner loop from --> for(int j=x; j>=0; j--) ?

[@MohakNigam-q5d]

@@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.

[@deekshithavarma3997]

j loop should be reverse order

[@AquaRegia-i3u]

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 💡

[@sourabhhukkeri8286]

wow

[@arnabdutta4662]

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 :)

[@subhashpabbineedi7136]

if you dont mind, can you send the code for tabulation

[@himanshu6665]

@@subhashpabbineedi7136 it is not mandatory to add this base case

[@devanshprakash8354]

​​@@subhashpabbineedi7136 fick tabulation only memoization

[@varunaggarwal7126]

the if condition will take care of this in recursion and memoization

[@jitendrakumar-vv8ho]

Actually i was wondering why t=0 case has not been taken care of

[@sumerrawat6947]

I love watching these 30 min videos that spend 40 minutes making notes !

[@OMPRAKASHSINGH-j5l]

Thank you for existing striver ! Helping others is the best thing any human can ever do! U are the best of our kind.

[@johncenakiwi]

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.

[@himanshuagrawal8012]

yes its correct, but we can say its exponential in nature

[@amanydv2112]

but here for index=0 the function would directly return target%arr[0]. for other index it complexity should be what you mentioned

[@ankishkhandelwal1061]

done this before 3 month after 3 month i Tried this question and boom got this easily u teach very well 👊👊

[@gaura-krishna]

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...

[@yaserahmed9721]

Wow i solved this problem today morning same way striver taught the previous topics!! You are rocking man

[@amanwarudkar9913]

Congrats buddy!!!!

[@varadthokal1406]

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

[@jaishriharivishnu]

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

[@suyashjain3223]

Getting better at DP day by day Thankyou Striver!!!

[@stith_pragya]

UNDERSTOOD.............Thank You So Much Striver Bhaiya for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@davidmwangi4312]

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.

[@vivekxdhiman]

Understood!! This DP series is magical! 💫🧿

[@ThatNibbah]

Understood to the Highest Level !!!!!!! Thank You Sir.

[@uttejdunga9795]

1D optimisation is great , loved it 👍

[@gaurabdas6503]

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

[@nainaprasad1174]

understood, i was able to write the recurrence solution without watching the vedio, thankyou striver

[@a_maxed_out_handle_of_30_chars]

this felt good to watch, thank you :)

[@ashwaniagrawal27]

this question blew my mind

[@rahatsshowcase8614]

similar to combination sum in your recursion playlist so this was easy for me !Us

[@AquaRegia-i3u]

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.

[@muditkhanna8164]

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.

[@dsp-io9cj]

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

[@umeshhbhat]

did you find answer for your query?@@dsp-io9cj

[@vikrambabariya5166]

Totally understood the concept, you made it easy for us! Thanks for all your efforts.

[@abhimanyuambastha2595]

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)

[@ScienceSeekho]

Thanks Striver

[@samyakjain7422]

understood...u r messiah in human form...best dsa content on youTube for sure.

[@vikasgupta6701]

Thanks for explaining with so much clarity. Able to do all recursion, memoization, tabulation and finally space optimization :)

[@shivamchauhan2267]

Greatly explained

[@hardikgaur5182]

For me , it is the best yt channel , for coding related stuff❤

[@satishsinghyadav4253]

His way of teaching never discriminates with a backbencher

[@adarshparitosh5870]

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 :)🙏

[@bhavuk2338]

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

[@narolavarshil6067]

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

[@JustGyan]

why we are not considering the base case of when target become zero?

[@kazuma0803]

Thanks a lot Striver, another question I was able to solve without seeing video just because of your old videos

[@AmanKumar-qz4jz]

i think ur god.....u came here on earth for us!!!

[@your_name96]

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.

[@yashaggarwal825]

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

[@binitkumar314]

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]

[@anweshabanerjee6241]

very much similar to combination sums that u taught..#striver takes us forward

[@ankitpandey7262]

UNDERSTOOD !!! 🔥🔥🔥🔥🔥🔥 As in DP19 similar this problem can also be done using only one single array ...

[@MohammadKhan-ld1xt]

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!!!

[@vaibhavkaul2029]

@@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.

[@priyanshkumar17]

@@vaibhavkaul2029 Yes, you're right. Thanks for this comment. You saved my time...

[@arjunkhanna1803]

NOTE FOR SELF: When sum of smaller coins any of the larger coin then dp

[@maneeshguptanalluru7807]

@Arjun Khanna Great! could you explain the intuition behind the above conclusion!

[@AMANKUMAR-eq6sq]

​@@maneeshguptanalluru7807 Greedy works perfectly in the case where law of uniformity is followed otherwise DP

[@prabhakaran5542]

Understood ❤

[@kumarakash5219]

I solved first dp question by myself ..ty striver ❤️❤️❤️❤️

[@jiveshanand5948]

Single row optimisation is the best..

[@katamsreeja6744]

Understood it clearly. Thank you so much.

[@cinime]

Understood! Thank you for your detailed explanation as always !!

[@ratinderpalsingh5909]

Understood, sir. Thank you very much.

[@kathanvakharia]

Understood...Completed (20/56)

[@kunalsaha9239]

Clean and clear explanation ☺️☺️. Understood 👍🏼👍🏼

[@ranasauravsingh]

UNDERSTOOD... ! Thanks striver for the video... :)

[@sumeetchawla3545]

Understood and really thankful for your great efforts.

[@mohitsingh13]

UNDERSTOOD ❤

[@adebisisheriff159]

Thanks soooooooooooooo much Striver!

[@hrushikesh-1914]

Understood. Thankyou sir

[@yashikajindal3758]

I solved this question on my own !!!😁

[@johnsimon8158]

Thanks for this awesome video

[@DevashishJose]

Understood Thank you so much.

[@techatnyc7320]

Thanks Striver!

[@mrinmoyhalder7293]

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

[@neerajjoshi8285]

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

[@AdityaPratapSingh-mb6jv]

@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.

[@AbhishekKumar-cv1dh]

Understooood 🔥🔥🔥🔥🔥

[@sahil01sn]

LC 322 and understood

[@karthikeyansivakkumar5075]

Understood Bro :) One Row solution is awesome :)

[@402saravana4]

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.

[@rishabhnema2479]

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.

[@NARUTOUZUMAKI-bk4nx]

UNDERSTOOD 🔥 😊

[@siddharth892]

Yesssss!!!. Did it on my own. Understood Sir ✅

[@RajeshKumar._.16]

for(int i=0; i

[@aasifali9139]

thx striver for this wonderful series.

[@RVcalisthenics]

understood striver😇

[@harshdeep7312]

ur content is my lob.

[@SumanSingh-gq5vn]

Understood sir!

[@anmolarora9419]

Amazing!! Just tired of scrolling Leetcode discuss, here is the best answer, Thanks!!❤🔥 🙌 💥

[@shaileshsingh6771]

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

[@johncenakiwi]

Thank you!!! Was waiting for this eagerly.

[@santoshb7776]

Understood sir .

[@striver_108]

understood striver bro

[@PIYUSH61004]

Understood man! Amazing work! Keep up the good work

[@sunilswami6796]

You r the best teacher brother🔥

[@harshitjaiswal9439]

Understood and great explanation as always!

[@GirishJain]

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

[@deepanshujain9962]

I was thinking the same. Thanks for pointing it aloud.

[@anuragprasad6116]

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]

@@anuragprasad6116 but what if target is 0 and index is not 0?

[@stym134]

@@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.

[@sayantabhattacharjee9808]

Awesome.....Loved it

[@rishabhagarwal8049]

Understood Sir, thank you very much

[@TON-108]

Understoooooooooooooooooooooooooooooooood!

[@stain0p101]

Understood.

[@taranjitsingh5158]

It is giving TLE in both memoization and tabulation

[@SatyamKumar-bw4vi]

UNDERSTOOD

[@manjunathg.s5967]

Understood!!! Striver rocks 😎

[@rahulchoudhary29]

Amazing content

[@dheerendrapratapsingh9406]

“Understood”❤

[@dhananjaygorain6375]

bro can you solve combination sum 4 using same concept leetcode 374 I guess . Cann you figure out why it is giving wrong ans below is the code class Solution { public: int combinationSum4help(vector& nums, int target, int ind, vector& dp) { if(ind == 0) { if(target % nums[ind] == 0) return target / nums[ind]; else return 0; } if (ind < 0) return 0; if (dp[ind][target] != -1) return dp[ind][target]; int pick = 0; if (nums[ind]

[@PrajwalCoding]

@@dhananjaygorain6375 You need to modify the code. This won't work because you have to calculate the number of combinations. Same logic will work but little modification on base case and the way you call it here pick = 1 + combinationSum4help(nums, target - nums[ind], ind, dp); needs to change to pick = combinationSum4help(nums, target - nums[ind], ind, dp);

[@rishabhgupta9846]

understood,able to solve by myself

[@mohitsingh13]

The DSA GODZILLA ❤🔥

[@navinpatil3983]

Thank you

[@sayakghosh5104]

Understood, awesome explanation as always.!

[@sanjanar9198]

Understood 🔥