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

Подписаться 635 тыс.

Просмотров 209 тыс.

50% 1

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

Опубликовано:

9 фев 2022

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 694

@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

@boyidapumohit4715 2 года назад

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 2 года назад

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

@inclinedscorpio 2 года назад

@@GajendraSingh-lv3jw or kitni reduce karega guru 😂

@krishnans1665 2 года назад

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

@deepanshudhakate9622 2 года назад

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

@iamnoob7593 7 месяцев назад

indeed

@CEOplays 2 года назад

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

@divyambhutani6229 2 года назад

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 🙇

@akr1831 2 года назад

There is no any Substitute of Your content on RU-vid. U r great ❤️

@user-zm9qn2sp3h 9 месяцев назад

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

@vikrambabariya5166 2 года назад

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

@user-nk1rc1fb7d Год назад

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

@vivekxdhiman Год назад

Understood!! This DP series is magical! 💫🧿

@suyashjain3223 9 месяцев назад

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

@gaura-krishna 2 года назад

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

@user-ie8sy7wo4m Год назад

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 💡

@sumerrawat6947 Год назад

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

@vikasgupta6701 Год назад

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

@ThatNibbah 2 месяца назад

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

@stith_pragya 7 месяцев назад

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

@arnabdutta4662 2 года назад

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

@a_maxed_out_handle_of_30_chars 9 месяцев назад

this felt good to watch, thank you :)

@ankishkhandelwal1061 2 года назад

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

@ScienceSeekho 2 года назад

Thanks Striver

@uttejdunga9795 2 месяца назад

1D optimisation is great , loved it 👍

@cinime 2 года назад

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

@kazuma0803 2 года назад

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

@katamsreeja6744 Год назад

Understood it clearly. Thank you so much.

@rahatsshowcase8614 2 года назад

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

@sumeetchawla3545 2 года назад

Understood and really thankful for your great efforts.

@kunalsaha9239 2 года назад

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

@johncenakiwi 2 года назад

Thank you!!! Was waiting for this eagerly.

@PIYUSH61004 2 года назад

Understood man! Amazing work! Keep up the good work

@johncenakiwi 2 года назад

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 2 года назад

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

@yaserahmed9721 2 года назад

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

@amanwarudkar9913 2 года назад

Congrats buddy!!!!

@JustGyan Месяц назад

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

@ranasauravsingh 2 года назад

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

@DevashishJose 7 месяцев назад

Understood Thank you so much.

@samyakjain7422 2 года назад

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

@aps8874 24 дня назад

Thank you so much!

@adebisisheriff159 7 месяцев назад

Thanks soooooooooooooo much Striver!

@kumarakash5219 2 года назад

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

@nainaprasad1174 2 года назад

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

@ratinderpalsingh5909 2 года назад

Understood, sir. Thank you very much.

@hrushikesh-1914 10 месяцев назад

Understood. Thankyou sir

@sayantabhattacharjee9808 8 месяцев назад

Awesome.....Loved it

@davidmwangi4312 9 месяцев назад

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.

@harshitjaiswal9439 Год назад

Understood and great explanation as always!

@siddharth892 2 года назад

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

@sayakghosh5104 2 года назад

Understood, awesome explanation as always.!

@SumanSingh-gq5vn 2 месяца назад

Understood sir!

@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

@anweshabanerjee6241 Год назад

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

@aasifali9139 Год назад

thx striver for this wonderful series.

@karthikeyansivakkumar5075 2 года назад

Understood Bro :) One Row solution is awesome :)

@NARUTOUZUMAKI-bk4nx 8 месяцев назад

UNDERSTOOD 🔥 😊

@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

@amithkoutinagaraj5419 Год назад

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?

@AbhishekKumar-cv1dh 9 месяцев назад

Understooood 🔥🔥🔥🔥🔥

@HappyHumbleHopefulHelpKey 3 месяца назад

Understood ❤

@113_manshi4 Год назад

Understood! Thank you so much!!

@abhimanyuambastha2595 2 месяца назад

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)

@saurabhrthakur 4 месяца назад

Understood!

@sunilswami6796 2 года назад

You r the best teacher brother🔥

@hardikgaur5182 Год назад

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

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

@satishsinghyadav4253 2 месяца назад

His way of teaching never discriminates with a backbencher

@ayushanand4337 Год назад

Why we are declaring the curr array outside of for loop unlike the previous questions where we did it inside the first for loop?

@rahulchoudhary29 6 месяцев назад

Amazing content

@raviparihar3298 5 месяцев назад

thank you sir

@pawanchandra9193 Год назад

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

@AmanKumar-qz4jz 7 месяцев назад

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

@rishabhjain1694 Год назад

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

@shresthjain7557 2 месяца назад

understood!

@gaurabdas6503 2 года назад

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

@pragyanandsingh6673 6 месяцев назад

Understood !!

@yashikajindal3758 19 дней назад

I solved this question on my own !!!😁

@sanjanar9198 7 месяцев назад

Understood 🔥

@stain0p101 10 месяцев назад

Understood.

@santoshb7776 8 месяцев назад

Understood sir .

@harshdeep7312 Год назад

ur content is my lob.

@coderrr3353 Год назад

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.

@vedantpatel5210 11 месяцев назад

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.

@dev-rock 2 года назад

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?

@RajeshKumar._.16 Год назад

for(int i=0; i

@striver_108 6 месяцев назад

understood striver bro

@rishabhagarwal8049 Год назад

Understood Sir, thank you very much

@mohdamaan5551 2 месяца назад

Understood..!

@narendramaurya4823 4 месяца назад

understood ... 👍

@reee896 2 года назад

So one case of no take was no coins were added but index moves to next position, Second case where we take the coins add +1 and the remain in the same index I thought there can be a 3 rd case where he take the coin and move to next value I thought there may be little back tracing Is it because we have to min no coins so that we keep on the same index till target becomes less current element

@abdurrazzaqqureshi4170 2 года назад

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.

@sauravchandra10 Год назад

Understood, thanks!

@anishkumarde5505 2 года назад

In the space optimized code if we take it then the formula will be 1 + prev[T-nums[i]] right?

@shubh625 16 дней назад

understood

@kathanvakharia Год назад

Understood...Completed (20/56)

@chirag5745 2 года назад

Hey Striver I have a very Important question If we present a recursive solution with memoization to the interviewer say in a faang interview is it going to be enough or we will need tabulation please answer someone very important doubt

@nithishlelll9664 7 месяцев назад

understood!!😄

@SatyamKumar-bw4vi 9 месяцев назад

UNDERSTOOD

@taranjitsingh5158 Год назад

It is giving TLE in both memoization and tabulation

@jeemains3524 Год назад

@arihantjammar8888 9 месяцев назад

Understood 😊

@your_name96 2 года назад

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 2 года назад

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 2 года назад

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]

@nehathakur40 Год назад

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?