DP 48. Matrix Chain Multiplication | MCM | Partition DP Starts 🔥
Вставка
- Опубліковано 30 вер 2024
- Lecture Notes/C++/Java Codes: takeuforward.o...
Problem Link: bit.ly/3nXqfce
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/take...
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the MCM Dp, this is the first problem on the pattern Partition DP.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.o...
You can also get in touch with me at my social handles: linktr.ee/take...
👏👏👏 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 ✌
arey aaram se bolo didi, ye beech beech mei daure pad rhe h kya!
@@momozkichutney 🤣🤣🤣🤣
@@momozkichutney wo stree h k6 v kr skti h 😂😂
Lgta hai didi zyda moody hai bich bich itna mood swings 😂
ye kya bawasir likh diya be
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 .
TBH for dp series Aditya Verma & you are the best. 😊
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 ❤️❤️❤️❤️
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
@@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 .
@@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
Its been 6 years since I came across this topic and finally understood it today
you've been unemployed for quite some time 😆
@@trijalsharma4471 solving a damn specific problem doesn't mean you are smart buddy.
That's the best video ever on Partition DP 👏 so much effort goes into making such content for generations, hats off man 👏👏
Understood
------------------------------
Recursion :-
TC---> exponential
Memoisation:-
TC---> O(N*N*N)
SC--->O(N*N) + O(N)
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.
I tried it multiple times earlier but now I got better understanding, indeed it will stuck in my mind now.
You didn't explain why you cant think in terms of the entire array.
Understoooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooood
MJHE BELEIVE NHH THA PHLE KI MAI YE TOPIC SMJH LUNGA EK BAAR ME .....BUT STRIVER MAKE IT EASY ......#UNDERSTOOD
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!!!!
Hi Striver, can you explain problems on pattern dp like burst baloons etc. Your explaination is very good btw.
Soon!
@@takeUforward jaldi le aao bhaiya, can't waitt!
Us
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
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.
❤️
I also
#include
int solve(int* arr, int i, int j){
if(i == j) return 0;
int mini = 1e9;
for(int k = i; k
size of array is n+1
UNDERSTOOD...Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Understood , difficult concept explained easily🤯🤯
understood that is not a question this a concept ....
hats off to your efforts man you are just amazing
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.
What an explanation....Partition was a concept i was not much clear with .....
Thank you for making me understand this concept
I'm blind...how am I supposed to watch this insightful lecture 🥺
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.
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...
Thank You
Understood!!!
Best Ever Explanation for MCM. Literally!
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❤❤
Awesome Just amazing lecture😃
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 🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏
thanks gyani baba@boomsi69
Understood Sir, Thank you very much
The code studio question is little bit changed now f(1,n,arr) will work instead of n-1
kya mast padhaya hai.....aapko dekhke mera khud padhane ka man hogya...❣❣❣❣❣❣
Thanks a lot for such a wonderful explanation sir :)
The Great Rohit Negi is here!
Rodriguez Kimberly Thomas Melissa Clark Ruth
Understood!!
my goodness!! crystal clear explanation I am grateful for your dp series, thank you, Striver.
DP Revision:
Forgot the concept so had to rewatch the whole video ;-;
Nov'20,2023 06:11 pm
how to solve the same problem starting from i = 0 , like in this question you have done with i = 1
Another great video, thanks striver for making me understand MCM
50 minute sound huge but it just flew by
areeee bhaiyaaa omphooo!!! zammmn bhai understood....saying this video is god damn amazing is an understatement.
Understood
Very clear and solid explanation,Thanks buddy
Understood ❤❤❤
Really nice explanation srtiver. I like the way that you teach and understood the MCM.Very tricky but now understood.
Understood
understood 👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍
after watching this video. New Courage Unlocked!
Moore Mark Hernandez Joseph Smith Dorothy
understood
if u can spare 1 hr, this video will fully make u understand the problem
How did you decide in tabulation
i from n-1 to 0 and
J= i+1 to n-1
Why j is not from n-1 to i or
i from 1 to n-1
Understoos!
Give this guy 10M subscriber by the end of the 2024
US❤ awesome explanation ❤
@striver Great explanation ... hope you will making a video on burst ballons and how to think for that problem ...
understood
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
understood
understood
Understood.🔥🔥Your dp series is best.
understood
why doesnt this work? can anyone tell me? its not passing any testcase!!
ll solve(ll i , ll j , ll arr[] , vector < vector < ll > > &dp){
if(i == j) return 0;
if(dp[i][j] != 2e9) return dp[i][j];
for(int k = i; k < j; k++){
return dp[i][j] = min(dp[i][j] , solve(i , k , arr , dp) + solve(k + 1 , j , arr , dp) + (arr[i - 1] * arr[k] * arr[j]));
}
}
ll matrixMultiplication(ll n, ll arr[])
{
vector < vector < ll > > dp(n + 1 , vector < ll > (n + 1 , 2e9));
return solve(1 , n - 1 , arr , dp);
}
please start new channel in hindi
learning dsa in hindi in another level of experience
UnderStood
Understood
Super Clear Understood.
Plz plz plz dp on graphs asap love ur work 🙏❤️
Clearly understood, thanks!
Thank you Sir ! Understood.
"US"
#understood
I had seen the video twice only then i understood the video well
in between the video I am getting very angry it is getting harder and harder to understand
It's hard but u have made it very easy to understand thanks bhaiya 😃😍
Nice explanation striver🔥🔥
Thank you so much striver ❤❤
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.
The notes for MCM DP are incomplete please sir do complete it as notes are very much helpful for revision.
where are the notes uploaded for DP series?
umm auxiliary stack space distracted me a bit XD
Understood completely!
Which application are you using to write on?
Amazing! understood
bhaiya bahut accha samjhaya....thanks a lot
sir what will be the exact TC of the recursive approach without memoization.
You cannot say exact TC of recursion, because it is generically exponenitation in nature as it tries all ways.
what arr[st-1]*arr[k]*arr[end] tells if any body understood please tell in comment
31:02 you can understand
what is the answer of your current range(st,end) arr[st-1]*arr[k]*arr[end]
what is the answer in left part
what is the answer in right part
@@upsolvecontest4677 it states the operations required to multiply the left part and the right part, once they have been individually solved
Bhai ek hi chiz ko kitne bae repeat kra h...faltu ka vidoe itna bada kr dia
Understood. Excellent explanation!
Understood. Helped a lot !
Hey striver ,i just come across to check your memorization code available at article of the same problem in dsa list and found that their is an error in your code as although you are checking for availability of precomputed (i,j) in dp by this : if(dp[i][j]!=-1)
but you forget to update it at the end with the value you are returning i.e.
return dp[i][j]= mini;
bhaiya tabulation khud se likh diya 😄
AMAZING EXPLANAITION AS USUAL!
thanks striver Understood!!!!
thankyou bro, very clear and easy explaination .
Best video I have ever seen on dp🔥
Please tell me how do i apply formula arr[i-1]+arr[k]+arr[j] on BCD recursive call because i is set to 0 index on BCD call
I found the solution which is that actually the whole array is passed in all the recursive call only pointer are moving that is i and j so there will always a arr[i-1] present in all the calls thats all.
understood the concept !!
All of your dp problems should have one playlist. It would be helpful.
It is there bro in a single playlist
Understood! Hats off🙏
Thank you so much bhayya ;)
Thank you soo much!! Please, keep posting such this amazing content!