DP 48. Matrix Chain Multiplication | MCM | Partition DP Starts 🔥

[@trex4997]

Bhaiya u r God sent angel. God heard the upcoming SDE's cry the whole nights, and then planted the idea of making DSA playlists in your head. Bowing to your intellect, dedication and hardwork .

[@OnstreamGaming]

the energy he dedicates in each of his videos is extremely commendable even at 2 am , 3 am, 4 am, he had made the video still so much energy and dedication.

[@gyanunlimited740]

Its been 6 years since I came across this topic and finally understood it today

[@trijalsharma4471]

you've been unemployed for quite some time 😆

[@codingalley6229]

@@trijalsharma4471 solving a damn specific problem doesn't mean you are smart buddy.

[@PankajYadav-zg1re]

Finally I got the exact idea how the recursion works in MCM problem , before your vdo I have watched a lot but didn't get clear idea ......You are awesome bhaiya ❤️❤️❤️❤️

[@ayushjain386]

Can you help me i am not understand steps= a[i-1]*a[k]*a[j]+func(i,k)+func(k+1,j) Why are again call function func (i,k)+func(k+1,j) again

[@sanketmudholkar2889]

@@ayushjain386 Because we have to compute the smaller part also like if we have (ab) and (cd) so we have to solve ab and cd seperately also .

[@prakharsingh9710]

@@ayushjain386 bro,suppose (AB)(CD) hai to finally AB * CD krne ka cost aaya hoga but (A*B) apne aap me bhi ek ques h n isko multiply krne me bhi cost aaya hoga to usko nikalne ke liye func(i,k) use kiya hai. Similarly, (C*D) ko bhi krna hoga jo ki other left over part hai partition ke baad to usko func(k+1,j) likha....! Thoda pen chalao or video waps dekho aajayega

[@anmolagarwal5950]

That's the best video ever on Partition DP 👏 so much effort goes into making such content for generations, hats off man 👏👏

[@ganeshkamath89]

Thanks Striver. Understood. 6 months back I had tried to learn it but I found it difficult. With your explanation I think I will remember how to do MCM and partiton DP.

[@digvijaysinghchauhan5795]

I tried it multiple times earlier but now I got better understanding, indeed it will stuck in my mind now.

[@madhuryareddy3994]

Thanks for existing man, you don't know how thankful I am🙏🙏you made this explanation such that I can never forget this concept in my life.

[@aayushisaha8]

👏👏👏 To everyone who made it this far !! And Double 👏👏 for those who didn't 💤 during this video . Cause it's a reallly long video ( ig mini movie 😅) . And just thinking of how much effort Striver bhaiya must have gone though to make it , edditing it , correcting it 👏👏 , Frankly speaking of me I dozed off 😪 a couple of times during the entire video 🤪 . But anyways Great Work , Striver bhaiya ✌

[@momozkichutney]

arey aaram se bolo didi, ye beech beech mei daure pad rhe h kya!

[@girishbhargava6367]

@@momozkichutney 🤣🤣🤣🤣

[@AshokKumar-ii4qr]

@@momozkichutney wo stree h k6 v kr skti h 😂😂

[@kon_humein]

Lgta hai didi zyda moody hai bich bich itna mood swings 😂

[@theexplorer9012]

ye kya bawasir likh diya be

[@stith_pragya]

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

[@DeadCode_Debugs]

i will tell again again and again this man is GOAT of dsa no matter what ppls are there in youtube who are teching dsa ,, he is always the goat

[@OnstreamGaming]

the energy he dedicates in each of his videos is extremely commendable even at 2 am , 3 am, 4 am, he had made the video still so much energy and dedication.

[@rishavsaha5254]

Understood. Before starting this topic, I had 0 knowledge about this topic, now after completing this video, I am taking the complete concept. Thank you so much for coming up with this amazing DP series striver.

[@krrajavlog]

❤️

[@rutwikmore7462]

I also

[@nowitspk]

Understood ------------------------------ Recursion :- TC---> exponential Memoisation:- TC---> O(N*N*N) SC--->O(N*N) + O(N)

[@mohitagarwal3639]

Hey Striver again thanks to you for teaching in such a wonderful way. I paused the video at 25:30 after understanding the approach to the problem and was able to solve upto memoization by myself. Thanks man keep up the good work.

[@sathwikabhignan1862]

my goodness!! crystal clear explanation I am grateful for your dp series, thank you, Striver.

[@shashwatdhingra3580]

Best Ever Explanation for MCM. Literally!

[@sameersahu4569]

What an explanation....Partition was a concept i was not much clear with ..... Thank you for making me understand this concept

[@dhikshithgoshika2700]

wah wah got the depth of deep recursion took me 2 days to completely write the total recursive code and understand .really striver bayya if you and your videos are not there many of us would leave hopes for preparing other companies , may god give you all the health and wealth bayya 🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏

[@Mr.Indianwxvhehsy9191hghgx]

thanks gyani baba@boomsi69

[@sakshigupta4793]

TBH for dp series Aditya Verma & you are the best. 😊

[@arijitdas4560]

understood that is not a question this a concept .... hats off to your efforts man you are just amazing

[@Noob_Coder1234]

HATS OFF TO THE GOAT STRIVER , HE HAD PUT LOT OF EFFORTS FOR US IN THIS VIDEO SO WE CAN UNDERSTAND THIS TOUGH TOPIC , REALLY AMAZING❤❤

[@chanchalroy3417]

Just understood the whole concept of partition DP at one go 🙌😌🔥

[@madhavdwivedi5146]

kya mast padhaya hai.....aapko dekhke mera khud padhane ka man hogya...❣❣❣❣❣❣

[@rohan8758]

Understood, I am feeling very sleepy, time is 2:11 AM but this video motivate me to watch it till i understand it completely, lot of Thanks @Striver for your DP Series!!!!

[@priyanshkumar17]

Excellent explanation - Partition DP Starts!!!

[@arnabsarkar5245]

Tussi great ho bhaiya, koti koti pranam aapko 🙏🙏

[@VinayKumar-ze2ww]

Another great video, thanks striver for making me understand MCM 50 minute sound huge but it just flew by

[@vivekpaliwal1876]

I like your vedios...your way of teaching is good...but 1 thing you can add at start of vedios that which application uses this algorithm just to increase interest in learning the algo...

[@dhirenpatil8600]

Really nice explanation srtiver. I like the way that you teach and understood the MCM.Very tricky but now understood.

[@deepti8920]

The best video on partition DP I came across! Good job!

[@108_adityakumar6]

Understood.🔥🔥Your dp series is best.

[@JothiprakashThangaraj]

Got it when going through coluple of times thanks a lot !!!

[@TXS-xt6vj]

Just like messi, no one can be better than this teaching, so underrated

[@cgoxo]

It takes a lot of effort to explain more than one example in detail. Thank you so much for this.

[@shivanssingh4897]

Hi Striver, can you explain problems on pattern dp like burst baloons etc. Your explaination is very good btw.

[@takeUforward]

Soon!

[@shreyasingh1258]

@@takeUforward jaldi le aao bhaiya, can't waitt!

[@aftabalam7103]

Very clear and solid explanation,Thanks buddy

[@rupamhari115]

MCM was always been a nightmare for me, and now, I finally understood. Thank you so much bhaiyaa!! 🙏🙏🙏🙏

[@adarsh_k_agrawal]

Understood LIS Pattern completely. Watching all the videos from the start of DP. It is really really helpful. Every concepts are clear and will surely finish the playlist. Thank you Striver, emiti amazing content pai.

[@ronakslibrary8635]

Understood , difficult concept explained easily🤯🤯

[@ritikshandilya7075]

Thankyou for amazing solution Striver

[@sumeetkumar4984]

bhaiya bahut accha samjhaya....thanks a lot

[@fmkhandwala39]

AMAZING EXPLANAITION AS USUAL!

[@anirbannaskar5495]

I have not seen such good explaination for this problem bhaiya, thanks for making such good conceptual problem!!

[@juniorboy1903]

It's hard but u have made it very easy to understand thanks bhaiya 😃😍

[@TXS-xt6vj]

No one can be better than you striver

[@ritwik121]

@striver Great explanation ... hope you will making a video on burst ballons and how to think for that problem ...

[@raghavmanish24]

MJHE BELEIVE NHH THA PHLE KI MAI YE TOPIC SMJH LUNGA EK BAAR ME .....BUT STRIVER MAKE IT EASY ......#UNDERSTOOD

[@sanskarkumar028]

very calm and easy solution . thanku u striver

[@cricketwala937]

this is the best lecture on MCM till the date . 🔥🔥🔥

[@JohnSnow-r1e]

Give this guy 10M subscriber by the end of the 2024

[@samyakjain7422]

areeee bhaiyaaa omphooo!!! zammmn bhai understood....saying this video is god damn amazing is an understatement.

[@rohitn6333]

Thanks a lot for such a wonderful explanation sir :)

[@parthsalat]

The Great Rohit Negi is here!

[@prettylilnerdy6802]

Nice tricks for solving all partition dp

[@shivisingh9975]

Understood! very well explained

[@suryanshsingh5304]

Understood! Hats off🙏

[@UECAshutoshKumar]

Thank You Understood!!!

[@suyashjain3223]

Amazing Explanation!!!

[@TXS-xt6vj]

Absolutely world class

[@cinime]

Understood! Thank you sooooo so SO much as always!!

[@gentleman7060]

All of your dp problems should have one playlist. It would be helpful.

[@arnoldsmith6584]

It is there bro in a single playlist

[@parthsalat]

I'm blind...how am I supposed to watch this insightful lecture 🥺

[@rohandevaki4349]

thankyou bro, very clear and easy explaination .

[@akashsri3]

The thing about him that his so authentic is that he actually solves the problem at point of time he does not not memorize the solution and show

[@manasranjanmahapatra3729]

Super Clear Understood.

[@sauravchandra10]

Clearly understood, thanks!

[@itishachoudhary906]

Thank you Sir ! Understood.

[@UCSDebajyotiDas]

The code studio question is little bit changed now f(1,n,arr) will work instead of n-1

[@Parthj426]

awesome lecture striver , understood

[@chandrachurmukherjeejucse5816]

Solved the question after watching just 15:43 all thanks to striver ❤

[@Zunan263]

Thanks a lot man plz donot stop ur series today there might be very less reach imagine after 6 months u will get shocked by reach just plz donot stop posting vedios

[@AbhishekYadav-rm4hw]

shouldn't the base case be if(j==i || j==i+1) return 0; as when j = i+1 then also there is only one matrix which is possible and then also we can't multiply. Edit: I appologize, I got it now

[@anonymousvoid6356]

Dont stop making videos man !!!!!!!

[@michael-pasquale]

Understood. Excellent explanation!

[@Zunan263]

Plz plz plz dp on graphs asap love ur work 🙏❤️

[@gauravbanerjee2898]

Thank you so much striver ❤❤

[@sukhpreetsingh5200]

Awesome Just amazing lecture😃

[@rishabhagarwal8049]

Understood Sir, Thank you very much

[@anukulgaurav3043]

Best video I have ever seen on dp🔥

[@siding6690]

#include int solve(int* arr, int i, int j){ if(i == j) return 0; int mini = 1e9; for(int k = i; k

[@RanjanSingh-wf9iq]

size of array is n+1

[@DevashishJose]

Understood Thank you so much

[@vishwasrajbatham5998]

Understood. Helped a lot !

[@ashishchourasia2830]

Hands down the best explanation.

[@TXS-xt6vj]

Legend , legend, legend

[@ektabansal7645]

Thanks a lot striver for this series, it is damn helpful!!

[@abhisheksinghdangi5027]

I have seen, revised twice the entire series till now and maybe will continue with this part later coz companies dont ask this hard for frwshers here.

[@bakyt_yrysov]

Thank you soo much!! Please, keep posting such this amazing content!

[@vidhigupta3769]

understood. Thanks Striver!!

[@OnstreamGaming]

Watched full episode of my Dp named Web SHow - THanks streiver

[@codelearner3355]

UNDERSTOOD ,THANKS!

[@blurrybrush1010]

finally,thank u striver for this series

[@ayonsinha2075]

bhai can you please tell me why i*j =n*n.....j==n that got it but why i is n

[@shubhadarajmane7323]

Thanks ,you helped me a lot.

[@prantikofficial]

Understood completely!

[@ratinderpalsingh5909]

Understood, sir. Thank you very much.

[@sanaaroraa9315]

Amazing! understood

[@anandpandey918]

Unbelievable explanation /* * Two matrices can be multiplied if and only if the number of columns * in the first matrix is equal to the number of rows in the second matrix. * * Let the matrices be: * Matrix A with dimensions m × n: m rows and n columns. * Matrix B with dimensions p × q: p rows and q columns. * * Resultant Matrix: * If Matrix A (of size m × n) is multiplied with B (of size p × q) * (where n = p), the resulting matrix C = A × B will have dimensions * m × q (i.e., m rows and q columns). * * The total number of multiplication operations required will be: m * n (or p) * q */ //Bruteforce Approach class Solution { static int matrixMultiplication(int arr[]) { /* * Call the helper function with the full range of matrices (from the first matrix to the last matrix). * The matrix dimensions are represented by arr[i-1] x arr[i] for matrix i. */ return minOperations(arr, 1, arr.length - 1); } private static int minOperations(int arr[], int start, int end) { // Base case: When there is only one matrix in the chain, no multiplication is needed. if (start == end) { return 0; } int minimumMultiplicationCost = Integer.MAX_VALUE; /* * Matrix Chain Multiplication (MCM) Problem: * Given 4 matrices with the following dimensions: * Matrix 1: A of size 10×30 (10 rows, 30 columns) * Matrix 2: B of size 30×5 (30 rows, 5 columns) * Matrix 3: C of size 5×60 (5 rows, 60 columns) * Matrix 4: D of size 60×80 (60 rows, 80 columns) * * We will have the following partitions: * * 1. Partition 1: A × (B × C × D) * - Step 1: Multiply B (30×5), C (5×60), and D (60×80): * B×C results in a 30×60 matrix. * (B×C)×D results in a 30×80 matrix. * Multiplication Cost = 30×5×60 + 30×60×80 = 9000 + 144000 = 153000 * - Step 2: Multiply A (10×30) with the result of (B×C×D) (30×80): * Multiplication Cost = 10×30×80 = 24000 * - Total Multiplication Cost for Partition = 153000 + 24000 = 177000 * * 2. Partition 2: (A × B) × (C × D) * - Step 1: Multiply A (10×30) and B (30×5): * Multiplication Cost = 10×30×5 = 1500 * Resulting matrix is 10×5. * - Step 2: Multiply C (5×60) and D (60×80): * Multiplication Cost = 5×60×80 = 24000 * Resulting matrix is 5×80. * - Step 3: Multiply (A×B) (10×5) with (C×D) (5×80): * Multiplication Cost = 10×5×80 = 4000 * - Total Multiplication Cost for Partition 2 = 1500 + 24000 + 4000 = 29500 * * 3. Partition 3: (A × B × C) × D * - Step 1: Multiply A (10×30), B (30×5), and C (5×60): * Multiplication Cost = 10×30×5 + 10×5×60 = 1500 + 3000 = 4500 * Resulting matrix is 10×60. * - Step 2: Multiply (A×B×C) (10×60) with D (60×80): * Multiplication Cost = 10×60×80 = 48000 * - Total Multiplication Cost for Partition 3 = 4500 + 48000 = 52500 * * Summary of Multiplication Costs: * 1. (A × (B × C × D)) → Total cost = 177000 * 2. ((A × B) × (C × D)) → Total cost = 29500 * 3. ((A × B × C) × D) → Total cost = 52500 * * Optimal Order: * The optimal way to multiply these matrices is (A × B) × (C × D), which gives the minimum multiplication cost of 29500 operations. */ // Iterate through all possible partitions to find the optimal way of multiplying. for (int partition = start; partition < end; partition++) { /* * NOTE: * In Partition 2: (A × B) × (C × D), the recursive approach helps break down * the matrix multiplication into smaller subproblems: * * Step 1: Multiply A (10×30) and B (30×5): * - This is done by the recursive call minOperations(arr, start, partition). * - The multiplication cost is calculated as: 10×30×5 = 1500. * - The resulting matrix has dimensions 10×5. * * Step 2: Multiply C (5×60) and D (60×80): * - This is done by the recursive call minOperations(arr, partition + 1, end). * - The multiplication cost is calculated as: 5×60×80 = 24000. * - The resulting matrix has dimensions 5×80. * * Step 3: Multiply the result of (A×B) (10×5) with the result of (C×D) (5×80): * - The multiplication cost is calculated as: 10×5×80 = 4000. * - This step is handled by the following code: arr[start - 1] * arr[partition] * arr[end]. */ int multiplicationCost = arr[start - 1] * arr[partition] * arr[end] + minOperations(arr, start, partition) + minOperations(arr, partition + 1, end); minimumMultiplicationCost = Math.min(minimumMultiplicationCost, multiplicationCost); } // Return the minimum multiplication cost for the current subproblem. return minimumMultiplicationCost; } } //Better Approach class Solution { private static int[][] cache; static int matrixMultiplication(int arr[]) { cache = new int[arr.length][arr.length]; intializeCache(); return minOperations(arr, 1, arr.length - 1); } private static int minOperations(int arr[], int start, int end) { if (start == end) { return 0; } if (cache[start][end] != -1) { return cache[start][end]; } int minimumMultiplicationCost = Integer.MAX_VALUE; for (int partition = start; partition < end; partition++) { int multiplicationCost = arr[start - 1] * arr[partition] * arr[end] + minOperations(arr, start, partition) + minOperations(arr, partition + 1, end); minimumMultiplicationCost = Math.min(minimumMultiplicationCost, multiplicationCost); } return cache[start][end] = minimumMultiplicationCost; } private static void intializeCache(){ for(int i=0;i

[@bishalpandit4464]

Great video! With great explanation

[@manasagarwal9341]

Just one doubt. Cann't be the best answer could be from multiplying non continuous matrices like multiplying matrix A and D , B and C and then [AD] * [BC].

[@culeforever5408]

Love you man

[@bobbysharma2495]

Very well Understood , since you were on a vacation, I thought why waste time let's learn MCM from some different guy, Aditya Verma was on the top searches, and OMG the roast..... at 00:37 hahahaha

[@tempbot7190]

understood bro!!!

[@rishabhbhatt9939]

sir what will be the exact TC of the recursive approach without memoization.

[@takeUforward]

You cannot say exact TC of recursion, because it is generically exponenitation in nature as it tries all ways.