Matrix Chain Multiplication | Dynamic Programming

Рет қаралды 25,310

Жыл бұрын

In this video, I will show you how to fill in the table for the Matrix Chain Multiplication problem. It uses Dynamic Programming. Matrix Chain Multiplication will allow you to multiply matrices together in a way such that the cost is minimum. Matrix chain multiplication is an optimization problem concerning the most efficient way to multiply a given sequence of matrices. The problem is not actually to perform the multiplications, but merely to decide the sequence of the matrix multiplications involved. The problem may be solved using dynamic programming. On the other hand, Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. Dynamic Problems come up a lot in computer science and programming interviews.

Пікірлер: 47

@colemanroy 7 ай бұрын

Exactly what I wanted, super straight forward and very well explained. Legend!

@QuocDatPhung 7 ай бұрын

Thanks Colemanroy! I'm glad it helps! Also don't forget to share with others! You can find the rest of my Algorithms videos in this playlist: kzfaq.info/sun/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

@nichilus806 Жыл бұрын

Great explanation/example. Brief but well done. My classmates and I thank you!!

@QuocDatPhung Жыл бұрын

Thanks Nichilus! Please kindly subscribe, it means so much to me! You can also find the rest of my Algorithms videos in this playlist: kzfaq.info/sun/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

@purifynature8479 Жыл бұрын

Thank you. This really helped me.

@shivasutube 2 ай бұрын

Simple and Clear explanation... thank you. Gr8 video

@QuocDatPhung 2 ай бұрын

Thank you Shivasutube! Don't forget to share with your classmates and kindly subscribe ~ you can find all of my CS videos in this link: kzfaq.info/sun/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

@mansibarewar6295 2 ай бұрын

i da bestt mann you cleared the doubt which other videos didn't

@QuocDatPhung 2 ай бұрын

Haha thank you! Don't forget to share with your classmates and kindly subscribe ~ you can find all of my CS videos in this link: kzfaq.info/sun/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

@spenter9570 3 ай бұрын

Great explanation, quick too

@QuocDatPhung 3 ай бұрын

Thank you Spenter!! I'm really glad you enjoyed my video! I would really appreciate if you could share with your classmates or kindly subscribe ~ you can find all of my CS videos in this link: kzfaq.info/sun/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

@vijei8963 7 ай бұрын

Thank you so much!

@QuocDatPhung 7 ай бұрын

Thanks Vijei! You can find all of my Algorithms videos in this playlist: kzfaq.info/sun/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

@lalith_kumar_akhila2411 10 ай бұрын

Saved my time 🎉 Appreciate it

@QuocDatPhung 10 ай бұрын

You're very welcome LalithKumar! Please kindly subscribe, it means a lot! Also, you can find the rest of my Data Structures and Algorithms videos here: kzfaq.info/sun/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

@lalith_kumar_akhila2411 10 ай бұрын

@@QuocDatPhung sure 😊

@QuocDatPhung 10 ай бұрын

@@lalith_kumar_akhila2411 Oh I forgot to mention, if you are taking Dynamic Programming (Analysis of Algorithms) which is a different course from Data Structures, here is the playlist for that course: kzfaq.info/sun/PLeTO6OT3-FKl-_EkIipoUmctPhvqiVPtY

@lalith_kumar_akhila2411 10 ай бұрын

@@QuocDatPhung Thank you, I'll go through it

@r.krisnamoorthir.k4622 2 ай бұрын

Thank you so much sir,

@QuocDatPhung 2 ай бұрын

You're welcome!! Please share with your classmates to help them in this course and also kindly subscribe ~ you can find all of my Computer Science videos in this link: kzfaq.info/sun/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

@gadithya4447 14 күн бұрын

could u share what tool you are using?

@QuocDatPhung 13 күн бұрын

Hi Gadithya! I use wacom tablet ctl 490 to write. I also use the Sketchbook app, OBS to record the screen, and Shotcut for editing. I hope that helps! Please kindly subscribe and share my videos it means a lot!

@soadscars4527 7 ай бұрын

Thank You

@QuocDatPhung 7 ай бұрын

You're welcome! Please kindly subscribe! As well, you can find all of my Algorithms videos in this playlist: kzfaq.info/sun/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

@badAtPickingUsernames1988 Жыл бұрын

At 5:45 how do we know 138 is the minimum cost?

@QuocDatPhung Жыл бұрын

Once you complete the table using the formula, the top right value is always the minimum cost. That is how the algorithm works. The proof for the algorithm is long and complex, so it's best just to know that the top right value is the minimum cost. Let me know if that helps.

@badAtPickingUsernames1988 Жыл бұрын

@@QuocDatPhung Yes. Thank you!

@iTube4U Ай бұрын

thank you or this, by the last 1,4 I did it my self

@QuocDatPhung Ай бұрын

You're welcome iTube! Please kindly share and subscribe~ you can find all of my CS videos in this link: kzfaq.info/sun/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

@aoyukialquen2835 6 ай бұрын

i have a question, why when i=j, we just fill it up with 0? can someone break it down for me please?

@QuocDatPhung 6 ай бұрын

It's over 2 years since I've taken this course but let's say i = 1 and j = 2. Then this means you're finding the minimal cost multiplying matrix 1 and matrix 2 right? Let's say that matrix 1 multiply matrix 2 costs 30, whereas matrix 2 multiply matrix 1 costs 20. Now, consider i = j. Here you only have 1 matrix. Nothing to multiply to. Therefore, the cost is 0. Let me know if that makes sense.

@aoyukialquen2835 6 ай бұрын

@@QuocDatPhung thank you very much sir, what about the reason we ignore m[2,1] ; m[3,2] etc? I'm sorry if I ask too much, I just want to understand... thank you in advance sir :)

@QuocDatPhung 6 ай бұрын

@@aoyukialquen2835 No worries! Now remember m(2,2) = 0 right? Because there is no cost when you only have a matrix 2 and matrix 2 only. Since there is only one matrix, there is nothing to multiply to so m(2,2) = 0. Now, what about m(2,1)? There wouldn't be any matrix to consider at all. That's why it's left blank. Let me know if that makes sense.

@aoyukialquen2835 6 ай бұрын

@@QuocDatPhung thank you sir, your video and explanation helped me, please keep going with the youtube videos, i support your channel! God bless you

@QuocDatPhung 6 ай бұрын

@@aoyukialquen2835 Thank you for your support! You can also find all of my algorithm videos here: kzfaq.info/sun/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC

@iTube4U Ай бұрын

Are u rep,ying with auto reply?

@QuocDatPhung Ай бұрын

Nope. I always redirect people to my CS playlist. Sometimes people watch something like Selection sort and they ask if I can explain QuickSort but they don't know that I already made it, in the playlist.