DP#3 : Change Problem-Minimum number of coins Dynamic Programming

Рет қаралды 235,275

5 жыл бұрын

Given coins of different denominations and a certain amount. Find how many minimum coins do you need to make this amount from given coins? Drawbacks of Greedy method and recursion has also been discussed with example
What is Dynamic Programming | How to use it
• DP-1: What is Dynamic ...
Coin Change Problem using Dynamic Programming:
• DP#2: Coin Change Prob...
See Complete Playlists:
Placement Series: • Placements Series
Data Structures and Algorithms: https: • Data Structures and Al...
Dynamic Programming: • Dynamic Programming
Operating Systems: // • Operating Systems
DBMS: • DBMS (Database Managem...
Connect & Contact Me:
Facebook: / jennys-lectures-csit-n...
Quora: www.quora.com/profile/Jayanti...
Instagram: / jayantikhatrilamba

Пікірлер: 288

@saadmanahmed860 5 жыл бұрын

faculty taught in class...i was total hogwash.. study books ..notes....didn't get anything.. search on youtube...i got tired.. at last..i got this video of this lady..just iconoclastic..such lucid illustration is rare.. thanks a lot..ma'm

@thiagoleobons390 4 жыл бұрын

iconoclastic?

@heimeinsheu 4 жыл бұрын

Mam can you check at weight 10 and coin domination 6.

@49sandeep 3 жыл бұрын

Perfect explanation...but one thing missed here...if suppose we dont have 1 Rs. coin..means if I have coins: [4, 10, 25] and amt: 41...how to calculate this matrix...there should always be one row with 0 coin...which can have max Infinity solns for each amount except 0 which would have 0 solns only. I think...thats should include in this video...Just my advice 😊😊

@shubhamupadhyay9308 2 жыл бұрын

@@49sandeep yes actually I also checked that but instead of initialising the whole 2d matrix with 0 you can try initialising with INT_MAX and when you will find min(INT_MAX, x) you will get the correct answer ;

@kkkkkt0359 Жыл бұрын

@vipinsahu1306 4 жыл бұрын

Jenny , You really made me learn the knapsack and cleary explained issue with recursion and greedy algorthin for such requirement

@alexb6568 4 жыл бұрын

I love you, Jenny! Finally a clear and lucid lecture on the subject.

@sureshchaudhari4465 3 жыл бұрын

Thanks Jenny Mam for sharing this lecture

@mnaresh3382 4 ай бұрын

small correction @7:27 the time complexity for solving through recursive approach is not 2^n, but rather 4^n for the taken example, In General, if we have m elements and we need to find for the amount which is taken as n, then we will have the time-complexity as n^m, where n is the branching factor

@arashbarmas4459 4 жыл бұрын

Loved it how you explain recursion first and connect it with dynamic programming. Thank you

@abolikhare2654 3 жыл бұрын

the way I thought problems should be studies from scratch and explained..you are doing the same thing...when I told my peers that I take almost around 4 hrs to solve a problem via analyzing they said I am wasting time..but the thing is without knowing basics it is pure rattafication....I am really happy to reach this channel!!!!!! thanks for making such in-depth analysis videos!!!

@bhogeswarasaikumar6351 5 жыл бұрын

Madam . Your way of teaching concepts is as beautiful as you. Excellent way of teaching. I was hoping more videos on Dynamic programming and Greedy algorithms. Mostly shortest path algorithms and graph theory related algorithms

@by010 3 жыл бұрын

Hands down the last explaination video you need for this. I had problems connecting logic on board with logic in code, simple code snippets are super helpfull (like column is j, row is i)

@arupbakshi484 4 жыл бұрын

This is a totally clear concept. I have seen many videos, they haven't any idea what r they doing! Thanks

@lumsism 3 жыл бұрын

It's mind boggling that this video is free! I mean i have paid for lessons on Udemy and i got nothing men! Was almost giving up until i got here..Great unparalleled explanation of dynamic programming on you tube! Thank a lot ma'am

@StringStack 5 жыл бұрын

intro is damn good and to the point... RESPECT.

@ksr11 4 жыл бұрын

Nice explanation. touched the main logic rather than keep on talking about formula. Also finally you talked about how to get those denominations also which is missing in other guys videos. Expecting more like this..Thanks.

@chetanpatil5925 4 жыл бұрын

Fabulous explanation!!!!! my all concepts are cleared now, thanks again mam for such beautiful explanation!!!

@sraynitjsr 4 жыл бұрын

Teachers Like You Prove That Only Those Who Don't Have In Depth Knowledge Doesn't Join Teaching for Comfortable Govt Job after Clearing Net or JRF. Our Education System Needs Updated Teachers Like You, Ma'am. In Colleges in India, Still Only Theory Theory & Theory is Being Taught and Students Find it Tough to Crack Product Based IT Giants Coding Round, I Wish there are More Teachers Teaching in Colleges Like You Ma'am.

@sraynitjsr 4 жыл бұрын

If Possible, Please Forward My Message to MHRD or Higher Education System, Our Teachers are So So Badly Back Dated, Teachers Must be Forced by Govt to Stay Up to Date With Technology Otherwise Just Theory Won't be Enough. This is not Just for Software Related Branches, for all Engineering Branches, Teachers Must Update Themselves on Regular Basis.

@shanmukhavarma3361 4 жыл бұрын

OMG finally understood the logic. Your are the best of all the you tube please also make competitive programming video means solving problem from code forces

@ibrahimghasia1909 Жыл бұрын

Thank You Ma'am. You have explained it so simply and easily.

@dhrumilsports3522 3 жыл бұрын

Teachers like you makes our life so much easy. Great !

@sunlight6 3 жыл бұрын

Thrkio

@Sumit-yn7dn 5 жыл бұрын

Great way of teaching and explanation is super cool ! you are beauty with brain.. and one more thing please try to make videos on competitive programming as well and try to make things clear by solving problems of different type . Thank you😊

@lochanaemandi6405 3 жыл бұрын

Wow mam... thank you so much... you are better than my professors. Also, thank you for drawing the parallels between greedy and recursion approach

@tlpunisher42 4 жыл бұрын

mam the way of teaching of your's is seriously awesome,i previously could't understand the solution of coin changing problem but after seeing your explanation it will be a dare to me to forget the solution ever.Thank You so much Mam for your explanation.

@asmasadat8082 3 жыл бұрын

So good explanation. I gave up on this problem because there was no proper explanation to this question. I am thankful to have found this video. Keep going :)

@aryanplayit02 4 жыл бұрын

Your solutions are very clear and precise, keep making them. Helped me a lot, will probably help a lot of other students too.

@sachinsingh1956 4 жыл бұрын

Ma'am your video on this particular algorithm become constitutive for me .

@akshaygoyal3782 4 жыл бұрын

Nice way of teaching. Thanks for this video

@rifairahman5329 2 жыл бұрын

Your lectures are amazing. Thank you, madam.

@InakiArzalluz 4 жыл бұрын

Awesome explanation, thank you so much!

@shilpasunil3458 3 жыл бұрын

Thank you so much for this wonderful lecture.

@priyangkumarpatel9317 3 жыл бұрын

Really nice breakdown of otherwise complex problem

@sudarsaps9916 3 жыл бұрын

Wow. Excellent explanation. No words👌

@ramankr0022 9 ай бұрын

Thanks a lot for the Table. Finally understood something, what was happening.

@aadityakiran_s Жыл бұрын

Excellent explanation. I wish though that you would have coded out all the other approaches as well (like regular recursive, top down, iterative among others).

@mananpandya4493 6 ай бұрын

great video and amazing explanation. Thanks for such good content

@user-rd5np4fs6b 6 ай бұрын

You are awesome! Crystal clear explanation.

@nikc5642 3 жыл бұрын

Awesome explanation Jenny! Sheer dedication of yours is commendable while explaining.. I do want to know how do we solve these kinds of problems during interviews because It may not feasible always to draw tables and spend time to calculate all that..Is there easy or better way to perform all that? Also the way you write 2 is very cute and also your last smile !

@kulkarnivedant 8 ай бұрын

no words to admire your teaching skills ^_^

@konandarkness 2 жыл бұрын

Amazing explanation. Thank you.

@sarveshlohani 4 жыл бұрын

nicely explained..thanks a lot..

@mohdarshad9427 3 жыл бұрын

great explaination madam, it help me alot in robotics and ai . i was searching on internet i hadnot found great explaination then i purchase the course of princeton university in 15 usd . it was completely worst . i was hopeless then suddenly your video come in recommendation regards

@geetarani-iu7kz 4 жыл бұрын

what will be the values for a[0][j] if we don't have 1 in coin denomination..

@vishukohli1109 4 жыл бұрын

You are just awesome mam....thnq so much😘😘

@adityakhare7073 5 жыл бұрын

What to do when no combination is giving us any of the sum from 0 to 10. Example:if we take set {2,3,5} and we want to have a sum of 10. In this case how to make the table? When will be at j=3 we will fill 0 for i = 2 and since it is zero (minimum) we have to copy it for i= 3 but by using 1 coin of 3 we can have 3 as sum. So what to do?? If any 0 comes we have to copy it to whole column under it???

@dhinasurya 3 жыл бұрын

what are the base conditions in this algo so that the output is correct. since we cant directly arrive at the first row values when we are provided with initial coin value other than 1.

@utkarshsrivastava9236 5 жыл бұрын

Best Explanation ever

@leelalekkala5587 Жыл бұрын

Thanks alot for this wonderful explanation

@salikayoub3341 5 жыл бұрын

i like u as a sis when u r tellng at terminl bye bye nd ur smile is superbb that tym ..rely i like u as a sis ..

@javi5296 4 жыл бұрын

wonderful explanation thanks

@patelbhai7340 3 жыл бұрын

It helps me to in my assigenment submission.thanks a lot for this video.....

@tolumideshopein 4 жыл бұрын

Would the approach to finding the used coins work always? for e.g. where the money(m) = 11 and we have coins 5 and 6 available?

@ramankr0022 9 ай бұрын

Thanks a lot for the video Ma'am.

@ananthareddy1890 4 жыл бұрын

Hi Mam Thanks for the video but there are a couple of things that i need to clarify.The Example that u have shown above does not have any repeated denominations and that is why i guess it worked perfectly.when u take the below example where denominations are {4,10,25} and the total amount is 41.SO the answer is {25,4,4,4,4}.But when we apply the above procedure to this example i dont where we can get the repeated denominations.Please let me know if this method only works if the lowest denomination is 1.

@mysterymidas8574 4 жыл бұрын

Best explanation for Coin Change. Way better than Tushar Roy and Back to Back SWE

@atulagrawal3757 3 жыл бұрын

how can we print the list of coins used in making the change? Like in making change of 40 if we have coins(1,2,5,10,20,25) involves two coins of 20

@lionesslady6795 4 жыл бұрын

well explained... thank you

@niazalmasum120 4 жыл бұрын

way of teching is beautiful

@shameemedayattu26 3 жыл бұрын

more informative lecture good, upload more videos like this

@mananmakwana4324 4 жыл бұрын

Mam , how to fill 1st row in the example with amount=41 and coins={4,10,25}?

@arunakirivenkatachalam5577 4 жыл бұрын

@20.33, I did not understand how to get which denominations gives the amount part. Can you please explain @Jenny? Or please provide me a link where I can refer this. Thanks

@c.danielpremkumar8495 4 жыл бұрын

At 27.20: Instead of two Fives, we can also use two coins viz: 1 and 9, in which case how would this alternative be traced from the generated table ?

@MR2FSD 3 жыл бұрын

The alternative "9+1" is being traced on the last row, when calculating the number "10" for the coin 9

@mousumiparida4256 3 жыл бұрын

nice explanation!thanks!

@amritanshusingh5945 4 жыл бұрын

at 19:05 in the table for coin of domination 6 and weight 10 value should be 5 in place of 2

@moinpatel938 3 жыл бұрын

ya you are right bro mam didnt noticed....

@Dexter_2503 Жыл бұрын

thank you bro i was checking the comments to see if anyone noticed but they were busy praising maam rather than notice something like this.

@alymtsumi4895 Жыл бұрын

@@Dexter_2503 Bro, I was doing the same thing!

@yashgiddia741 2 жыл бұрын

Excellent explanation

@ashishsingh-vr5dx 5 жыл бұрын

Even being from top a NIT ,you are better than my teachers. Thank You 😊

@mental-block 4 жыл бұрын

Hi Jenny, Thanks for the video. At 14:46 when you are referring to above cell there might be a chance we can go array out of index if i==0. Are you using 1 array for coins and 1 array for amount or you are using 2D array?

@sanjaygodiya4443 3 жыл бұрын

Absolutely it will throw ArrayIndexOutOfBoundsException on the very first loop when i=0 because in if block there is a[i-1][j]

@vinayak186f3 3 жыл бұрын

@@sanjaygodiya4443 isn't the condition wrong ? If we have coins with value less than j(sum) then we won't be able to use them , right ?

@bhuwanmalik2034 3 жыл бұрын

I want to know how f(0)and f(1)are stored in memory of memo(n) in fib series using dynamic programming

@akashkumar-nr6jk 6 ай бұрын

Amazing Explaination MAM 👍👍

@singhsengar1 3 жыл бұрын

will this algo work if you have no coin with value '1'. ie smallest coin value is say 2.

@kundankumar-up4ln 4 жыл бұрын

Sometimes your algorithm shows arrayoutofbound exception. So can you please show us the glimpse of whole code in the last of vedios so we can take the screenshot of the code

@mohammadkarami8984 4 жыл бұрын

Great Video! Thanks a lot. Can you please use a smaller example for your future videos?

@sureshchaudhari4465 3 жыл бұрын

I got the explanation but how in dp I will conclude which row column i should refer for various dp problems

@dibyajyoti_ghosal 4 жыл бұрын

Can you show us a way of how to transform this into a 1D array? Since that will save space and the program will run much faster.

@sanc7897 7 ай бұрын

You are god's gifted 🙏

@NepalNabin 2 жыл бұрын

Great video. I have a question. Why do we copy from the above cell, if the coin value is greater than the sum? To get to the sum of 1, how can we use use 1 no of 5 coin? Or to get sum of 2, how can we use 2 no of 5 coins? Cannot make sense of that.

@chiragjethava1186 4 жыл бұрын

what will if we don't have denomination of coin 1?

@RDJ499 9 ай бұрын

mem ye side me jo aapne equations vo bhi paper mai likh ne hai ya phir table se sirf find karna hai ?

@MrMutant-v1h 5 жыл бұрын

Thank you dear mam 😊

@apnateam Жыл бұрын

so many people come up with the name like striver ,Lover Babbar , Abdul Bari sir. Very few know about her . What a Teaching style mam . Thank you for clear and crystal concept. Her Dsa playlist was also mind blowing.

@adarshbhandary4512 3 жыл бұрын

what if there was no 1Rs coin.? how to fill the initial rows in this situation.?

@ramakrishnareddy782 3 жыл бұрын

Hi Mam, Thanks for the video. Is there any steps to find max number of coins in this problem

@sanjayijju4996 4 жыл бұрын

If there is no 1 rupee denomination how you are going to take the first row values. plz let me know

@bhumikaailawadi5850 2 жыл бұрын

why in 0/1 knapsack for remaining capacity we take values of previous row, but here we take the values of same row??

@finchien 2 жыл бұрын

although it's hard for me to understand the English accent but still useful and clear with illusion. thanks!

@rahulsrivastava7017 3 жыл бұрын

mam in the example while using DP we get the solution as (5,5) but another solution can also be (1,9) . So how do we get that one ??

@tejasnikam3287 4 жыл бұрын

Ty for your efforts

@NikhilKumarrocks 4 жыл бұрын

hi here we got the count of minimum change.......but what the logic for finding the coins values counting up to minimum change

@sachinsingh1956 4 жыл бұрын

Ma'am there is something wrong in calculation we can make 6 by Using two ways but you write 3 ways.possible ways are (2,2,2,) and(3,3).

@vivekkumar-cz2qc 4 жыл бұрын

what will happen if we do not take one rupee coin then how we will fill our first row and which algo we will use to fill.

@UtkarshTyagi 3 жыл бұрын

What if we don't have the denomination of 1? How will we initialize in this case?

@manishkc3852 5 жыл бұрын

there are two cases of choosing two coins, first is (5,5) and another is (9,1) to make sum 10. Right?

@ikhariyafaizal6281 Жыл бұрын

But (5,5) is optimal solution as it uses dynamic programming. Whereas, if we use greedy technique, (9,1) is correct answer.

@ayanbiswas6849 4 жыл бұрын

at 24:45 if j < coins[i] then we are simply copying the above cell but what about the first row where we don't have any cell above??

@idk_47 4 жыл бұрын

for(int j=0;jj) arr[0][j]=0; else if(j%coins[0]==0) arr[0][j]=1+arr[0][j-coins[0]]; }

@techservicebangla7126 4 жыл бұрын

If we don't have coins 1. Suppose we have coin 2,3,5,6. And we want to make amount 10. Then j value will be 0-10. In this case when j=1, what will be value of a[i][j]? when j=3 or 5 for coin 2 , what will be the value of a[i][j]?

@divyakriplani1544 3 жыл бұрын

What if there is no coin of denominaton 1 then how you will solve this ?

@juanherrera3919 2 жыл бұрын

I have a problem and I don't understand, how can I do it? Modify the DPChange algorithm to not only return the smallest number of coins, but also to return the correct combination of coins.