34 Matrix Chain Multiplication Recursive
Вставка
- Опубліковано 4 лют 2020
- Matrix Chain Multiplication using Recursion
Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.
PROBLEM STATEMENT LINK:www.geeksforgeeks.org/matrix-...
Playlist Link: • Dynamic Programming | ... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
(1)= Intro
(2)= knapsack Intro
(3-12)= 0-1knapsack
(13-17)= Unbounded knapsack
(18-25)= Longest Common Subsequence types
(26-32)= Longest Palindromic Subsequence types [part of LCS]
(33-45)= Matrix Chain Multiplication
(46-50)=Binary Tree regarding DP
Bahut bahut dhanyawad
Helped 👍🏻
what about the other parents Q he talked about in 1st video LIS, kadane's algo, DP on grid, Fibonacci ..
@@divyanshuupadhyay9831 yeah same doubt
itna berozgar hai bhai tu ki yehi sab karte rahta hai
Correction:
07:22
The value is actually 27,000. So making (ab)c the smaller and preferable choice at 4500. Everything else is same, just the choice will be different...
Thanks
Thank You ... Was confused
Despite of the hold on concept what makes this channel standing out to others is the energy level and enthusiasm of bhaiya unlike most of other youtube channels where they all sound sleepy or dead. Thanks alot
Fir bhi app english me Likh rhe ho🙄
@@ytg6663 what it has to do with english?
@@mradulagrawal1579 placement ho gya kya ye btao
@@ytg6663 lol
At i == j the cost is zero not because there's only one element in the array. It'll be because there's no other matrix to which the remaining matrix will be multiplied
Ex. [10, 20]
Here i = 1, and j = 1. So, there's only one matrix in the array and no other matrix to which this matrix can be multiplied. So, there will be no multiplication, hence the cost of multiplication becomes zero
thanks for explanation
Thanks brother
at one element we will have that i>j case
This comment needs to be on the top, so that nobody misses out on this minor yet important detail.
Ty
Thank you so much ...this DP series is helping me a lot 😊
I am glad it helped you!! Help this channel grow by sharing it so that this content can help more students like you !!
Coding Ninja is showing their add on this video.
Lol , as if I will buy any course after experiencing how Aditya teach.
haha 😂😂 poor them 😅
I am coding Ninja employee reading this lol .. :)
@@mohdsaif7834 sam here 😅
@@mohdsaif7834 learning how to teach mcm in true way
@@mohdsaif7834 so what?? He teaches far better than coding ninjas!!!
33 of 50 (66%) done! A long video, but was worth it to understand the range of k. I have seen many versions, some using gradually incr len of sliding window, etc., but this one is more clear. I use terms lo and hi instead of i and j for easy readability.
Bro for backtracking also tell any series so i can follow
@@thinkingmad1685 kunal kushwaha
These lecture series are like The New Testament of Dynamic Programming. It is going to serve the generations to come. Great work and huge thanks.
Until Exodus.....
I don't think so.These are quite time consuming.
Papa ki pari thinks world is like a disneyland. Read about that testament and Goan Inquisition. Dumb Girl
right!!!😃
Your series is the benchmark in explaining dp concept. No one on earth explained it better.
Sir , you're a LEGEND ! Thank you for helping us .
Thank-you so much for all series, especially for making us understand with dry running.
Trust me, this is the *best* matrix chain multiplication dp explanation on the whole internet.
Can u pls tell where did u learn it from? I just wanted to know whether u learnt from books or some teacher.
Thanks again!
Would you believe me If I say I did that on my own?! Because I did. 😅
Teacher and books cant teach you the way you want to learn tbh !! Self Study is all that I believe in, so keep digging into stuff, you will learn stuff that no one has ever learned or know of before !! Sometimes you just have to be the person 0, no teachers no books.
Do share the content to help the channel grow !!
@@TheAdityaVerma Thanks a lot for the reply - it enlightened me!😇
Will surely share this channel with my whole class👍
@@TheAdityaVerma bhaiya LIS ka versions ka video bhi upload kar dijiye
@@ankurkumarupadhayay4304 code for cause channel py dekho acha smjhaya hein
@@TheAdityaVerma You're the best teacher, I've ever had. Never thought someone would teach me this topic like this, it feels like my college friend is teaching me, in fact even better.
sir i beg you please cover more topics....It's beacause apke saath aisi frequency match ho gyi hai that i cannot even express please please please please...Its a humble request
recursion is seriously a magic we are not telling it to multiply a[i-1]*a[i] and it is doing that by itself seriously I am amazed to see recursion!
Same
i am beginner in competitive programming but after going through this playlist i cant say that anymore.
THANK YOU bhaaaaai!!
You are helping lots of people by teaching the dynamic programming so easily and clearing the concept.
Very nice explanation. Please make a series on strings and graph also as interviews have good questions from these topics. Your way of explaining concepts is really good.
I seldom find videos where I understand the concept better than through CLRS. Your MCM video is one such.
On 33 out of 50. Best playlist of DP, best than all free and paid resources available for DP
Thanks Aditya again. Putting in some simple term that I understood. Taking an example we want to multiple : A*B*C*D*E
Here K is nothing but a pointer that decided the group split. Imagine that as a pointer in above example and try to split in two groups.
So first we split the whole thing in groups, and again in small group and so on until we get single valid input, then return that value . Return answer and keep taking smallest from each split.
Ex :
Group 1. : A*B
Group 2 : C*D*E
so solution will be : Cost of Group_1 + Cost of Group_2 + Cost of Group1 *Group2 .
We all know that for matrix multiplication : (10*30 ) ( 30*40 ) => 10*30*40 , which is row_group_1 * row_group_2 * column_group_2
in the recursion for loop, third term is something that will generate the value and return since it has the actual formula of the matrix multiplication of smallest valid input : so recursion(group1) + recursion(group_2) + row_group_1 * row_group_2 * column_group_2 .
Happy learning :)
Thanks man
I understood this expect for recursion(group1) + recursion(group_2). Why did we have to add these?
@7:23 the value should be 27,000 instead of 2700 I suppose.
18000 + 9000 = 27000 , i also think that
Yes
@VASU BANSAL I think you are doing Phd on Mathematical Calculations , You don't worth these level of content.
@@shubhamkeshri8430 Vasu is just pointing out a little mistake. That doesn't means that he don't like the video. So please stop acting like a kid.
@@shubhamkeshri8430 and i guess you are doing PHD in trolling
energy was awesome and loved how you explained every small ( necessary )detail in it. :-)
dude your explanation cleaned up my room of dp and now everything is aligned perfectly , before this video i knew MCM ,but it was plastic, now its concrete.
Explanation is just amazing seems like my friend is explaining.... I've seen many videos of this topic and all the time I got more confused but on this channel it seems that topic is quite easy..... You are amazing ✌
Loved your way of Explanation. Simply Good.
Thanks a lot sir i would have never even touched dp if it werent you. Great work
Great Work bro...........!Please upload more videos related to dp on grid,kadane's Algorithm,LIS etc.😊😊
explained very well from where and till where to run for loop and and value of k. It will be useful in solving other questions as well.
Bhai video dekhne ke baad, I had the 'aha' moment.. Literally how you connect the dots at the end and generalise the concept - you're the best... I'm sharing this with all my friends
There are so many questions on leetcode that uses this model - burst balloons, minimum cost to merge stones... Aapne toh saare banva diye, jisme pehle kaafi time waste kiya hai maine...
Thank you so much for this series
Thanks Arijit, I just tried to give my best !! Its 1am, I really appreciate the hard work your putting in. Wish you luck brother !!
@@TheAdityaVerma Thank you so much bhaiya, abhi toh aapki poori playlist complete karni hai mujhe!!!
Saachme best lectures on DP!!
@@royarijit998 what all questions you found on leetcode related to this?
@@royarijit998 How did you solve those questions? I tried solving them but getting some error.
leetcode.com/problems/burst-balloons/
@Arijit Roy I am not getting correct ans in this problem .. can you please share your code in this problem?in c++
It took me time to understand how the loop would work to find different cost by looping over k values. If the example taken would have 6 array items instead of 5, it would have been easier to comprehend the loop.
Enought of the rant. I should admit, I am amazed by how quickly i am going over dp questions. Truely amazing work Aditya. Thanks alot.
Congratulations sir on 10000 subscribers😊
Abhi to bhut aage jana hai!
Sir recursion or backracking per bhi videos banao na please!!!
Thank you so much .Plz plz plz continue till all variation of question as you said in this lockdown time .
I will try my best
phli baar me smjh nhi aaya! Frustration hua par doosri baar patience se suna tab smjh aaya...bht accha explain kia hai bhaiyya ✨✨✨✨✨✨
Anyone knows why videos are not coming now. His explanation is super best never seen such kind of tutorial. You are the Best. ❤️
This series is GOAT!
where is my sheep?
I don't know what all I have tried to improve my dp skills but was not able to be confident at it, but this tutorial like really helped me .Thanks a lot ,Keep up the good work
You're correct when you say "Isse achese shayad hi koi samjha paye"
Beautifully Explained
For the first time in my life iam watching all the adds that coming in between videos just to support gem of Dynamic programing.❤️
Just remember his name Aditya verma ❤️....No more words
You're Awesome Dude !
dude..use brave browser ..no ads , it helps to concentrate and you will be watching continuously with full focus on the target.
@@AbhishekKumar-im2xd same
@@AbhishekKumar-im2xd you didn't get his point
this channel deserved at least 1M subscriber.
Thank You so much for this amazing Content.
Thank you. This is the least I can do on all of your videos
Good explanation brother.
Thanks for making hard topic to very easy
Without Any Doubt One more amazing Lecture
bhaiya u teach far better than gfg wale sandeep sir,means any student can not only learn but also develop the thought process....u r grt bhaiya
best ever channel for CSE on youtube.☺
Confidence increasing element you are. Love you
Aditya Bhai, everything is great in this video each and the way you teach is super excellent. Before I was very scared of recursion and DP. I tended to leave any problem I encounter with DP or recursion. But after watching these videos, I can confidently choose any DP or recursion problem and can try to solve it. Thanks a lot, Bhai.
14:48 Python coders TRIGGERED!!!!
True LOL. I am also using python....
best dp series on UA-cam❤️
awesome explanation. Please make videos on other topics as well
Never seen this much of clear thinking in programming!
Thank you very much. You are a genius.
At 25:02 20*30 bhi include hoga.Thanks a lot the video.Really helpful
But loop k = i+1 se start hoga, aur a[i] = a[i-1] *a[i]
Bhai Mja aagya.... I regret why didn't I find you early....
If you're taking j=sizeof(arr) then k
yeah why is that in the video he clearly took j as the last element in the first approach
Thank you lot of sir this video series really lot of help me for doing competitive programming 😇😇😇
Nicely explained bro !!
Thanks brother, Do subscribe and share, that keeps me motivated to do more !!
this guy is a beast
Awesome teacher🤗
can you please make a playlist or graph theory too..it'll be of greattt help !
Plz start a series on graph and advanced number theory🙂
In the base condition when i==j, it means that both are representing the same matrix. i.e. There is only one matrix remaining and we require two matrices to multiply.
Therefore we return 0 when i==j, not because there's one element in matrix.
It would be great help if you can explain the question of print parenthesis in MCM like what changes to be made.Thanks in advance! :)
can't we make (using extra space) pairs of all the Ai 's such that each pair contains row and col details of the matrix, and then apply the solve function?
Never thought that the balloon bursting problem was actually a variation of MCM.
Yeah it kind of is !! It was in my list, but had to drop it off due to time shortage.
@@TheAdityaVerma are you planning to make video on LIS ??
@Najim Choudhary is word break also a variation of mcm?
@@atharvjoshi682 yeah it can be done using that
Value of k will be in range i to j as range function in python doesn't take last value into account.
So. for k in range(i,j):
temp = solve(arr,i,k)+solve(arr,k+1,j)+arr[i-1]*arr[k]*arr[j]
Thank You For This Vedio!!!
Love you ❤️❤️ Sir
chilla chilla kr saari scheme btadi sr apne!
For every call value of mn will be INT_MAX so how the value of mn will be updated since the min function is comparing INT_MAX and tempAns value everytime?
i think think the INT_MAX is only for 1st iteration of for loop, basically the whole finding minimum process is only for comparison among the iterations of the for loop at every level of recursion
please also make a tutorial on how you rotate your pen on fingertips..
#python program
#Matrix chain multiplication(Recursion):
import sys
a=[40,20,30,10,30]
i=1
j=len(a)-1
def mcm(a,i,j):
if i>=j:
return 0
mi=sys.maxsize
for k in range(i,j):
temp=mcm(a,i,k)+mcm(a,k+1,j)+(a[i-1]*a[k]*a[j])
if temp
Gadar cheez h bhai ye MCM to 🤯
At 21:34 , from k+1 to j , I think we'd have 3 Matrices namely [ 20 x 30 ] , [ 30 x 10 ] , [ 10 x 30 ] , Similarly at 25:07 too.
Kindly correct me if wrong.
I too had the same doubt
Ai = arr[i-1] * arr[i]
K+1=3 then from k=3 to 4 there are two matrix
21: 34 yes we have 3 matrices but at 25:07 ig we have only two because the loop starts from k = i+1 , so 30*10 and 10*30
awsome video
nice explanaion
19:48 A video on how to roatate pen like Aditya Verma is much needed !!
Kya batate ho aap wow!!! Love you. #dpking
thank you sir
Thanks !
Everything is good bro, concepts are good, explanation is good, methods are good except arrogance. Like I am best others can't teach you better than me.
Bro 23:38 pe 10*30 vali matrix kyu aa rahi h ?it reaches the end so NULL nhi hoga..
please tell
@24:15
The example you have taken for that when we call k+1 to j there k+1 which becomes "i" for the next rec call becomes equal to "j" which is taken care by the base condition. so can we not make it till j-2 since the one we took was redundant
I have same doubt, please clear my doubt if you can🙏
Recursion return kaise karega phir... Bas condition pe return karta hai
Fucking Great Playlist!!!
Best one ever.
Keep up the good work.
one thing when i=j that doesnt means we have size=0 , will that doesn't mean that we got only one element and thus zero operations required .. correct me if I m wrong
I have a doubt, when you set k =I+1, and break
i -> k-1
k->j
Here since i started from 1, zeroth index value in array will be missed, since first partition will only cover 1-1 not 0-1 indexes.
Am I missing something
sir ji ap ki video dek ke to DP acha hogeya au pen ghumana bi ache se shik geya .😀😀
Shouldn't we declare the mn=INT_MAX globally?
I am getting confused that mn will get initialized to INT_MAX in every recursive call then how can it keep the track of minimum value?
Ya same doubt
Just think in this way that after all the function calls when the control will come to taking min for the last function in the stack it will take min value and return that value to second last function which is waiting for its child to finish , after getting the min value from its child it will also do the same thing and finally the function called from main will return the ans
You cannot declare globally because for every function call you are not getting the value of temp ....since temp is dependent on its child function calls ....first time temp will hold any value is when the last child finishes its call.
Hope you get it.....keep learning 😀
nice solution
nice one
I have been watching all your vids in x1.75 now your normal voice sounds so strange to me
Thanks bhai ❤
started first video on 30.01.2023. watching this on 22.08.2023. Will finish the whole playlist before sleeping today.
Please make a video on Soduko solving problem
Just one doubt. Shouldn't there be no "loops" used in a recursive solution? Am I missing something here!? Please let me know.
Why we are concerned with minimizing only multiplication operations in the multiplication of 2 matrices? Is it because it is a costlier operation than +? or multiplication happens more times than addition?
Because multiplication varies according to their order but addition and subtraction is just fixed ... you can change their order of addition but their is no changes occurs in the result. So, I think it's worth enough to calculate the right approach for multiplication .
jahapanah tussi great ho
why cant we have k= i to j. Bcz when we can have answer as (ABCD) and condition i>j will automatically give answer 0 when k+1 > j
Because in that case recursion will bring you back to the same bigger problem and it will result into stack overflow error
Vha bhaiya kya pdate ho 🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥✌✌✌🙂🙂🙂🙂🙂🙂🙂🙂🔥🔥🔥🔥🔥🔥thank u so very much .
before watching the video my thought was this video is too long for the question and after watching this video my reaction was how can someone tech all these concepts in just 40 minutes...great video💓💓💓