Matrix Chain Multiplication | Dynamic Programming

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.

[@colemanroy]

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

[@QuocDatPhung]

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: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@bilalsultan1130]

Great explanation. And very quickly. Best explanation I've ever seen. I also subscribed your channel.

[@QuocDatPhung]

Thank you so much! If you know anyone taking the class who needs it, please kindly share it with them ~ you can find all of my CS videos in this link: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@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: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@gadithya4447]

could u share what tool you are using?

[@QuocDatPhung]

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!

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

[@mansibarewar6295]

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

[@QuocDatPhung]

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: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@marcugusan8222]

👍

[@QuocDatPhung]

Thanks Marcu! Please subscribe and share with your classmates :)

[@r.krisnamoorthir.k4622]

Thank you so much sir,

[@QuocDatPhung]

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: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@net.navigator]

the legend. thx man

[@QuocDatPhung]

Thanks Net Navigator! Please kindly share with your friends and subscribe to support me (it means a lot) ~ you can find all of my CS videos in this link: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@coolestclipsontheinternet]

simple enough

[@QuocDatPhung]

Thank you! Please kindly share with your friends and subscribe to support me (it means a lot) ~ you can find all of my CS videos in this link: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@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: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@SaraKhan-zk8ep]

Best best best 🥹🤌

[@QuocDatPhung]

Thanks Sara Khan! Please kindly share with your friends and subscribe to support me (it means a lot) ~ you can find all of my CS videos in this link: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@SaraKhan-zk8ep]

@@QuocDatPhung I'll surely watch the playlist 😊😊

[@shivasutube]

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

[@QuocDatPhung]

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: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

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

[@aoyukialquen2835]

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

[@QuocDatPhung]

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]

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

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

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

@@aoyukialquen2835 Thank you for your support! You can also find all of my algorithm videos here: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@ethanhyde3872]

Better than Abdul!

[@QuocDatPhung]

Thank you Ethan! Pleased kindly share and subscribe~ you can find all of my CS videos in this link: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@purifynature8479]

Thank you. This really helped me.

[@KhoiNguyen-et1uw]

Jesus bro, thanks a ton

[@QuocDatPhung]

You're very welcome Khoi! You can find all of my Algorithm videos here: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@lalith_kumar_akhila2411]

Saved my time 🎉 Appreciate it

[@QuocDatPhung]

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: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@lalith_kumar_akhila2411]

@@QuocDatPhung sure 😊

[@QuocDatPhung]

@@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: ua-cam.com/play/PLeTO6OT3-FKl-_EkIipoUmctPhvqiVPtY.html

[@lalith_kumar_akhila2411]

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

[@vijei8963]

Thank you so much!

[@QuocDatPhung]

Thanks Vijei! You can find all of my Algorithms videos in this playlist: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@nomankhan7190]

WellDone.

[@QuocDatPhung]

Thanks Noman! If you enjoy my Algorithm videos, you can find the rest of them here: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@soadscars4527]

Thank You

[@QuocDatPhung]

You're welcome! Please kindly subscribe! As well, you can find all of my Algorithms videos in this playlist: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@zihanzhou5812]

Good

[@QuocDatPhung]

Thanks Zihan! Please kindly subscribe. You can find the rest of my Algorithm videos here: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@spenter9570]

Great explanation, quick too

[@QuocDatPhung]

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: ua-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html