Matrix Chain Multiplication Dynamic Programming
Вставка
- Опубліковано 25 сер 2024
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, you will learn about Matrix Chain Multiplication problem using Dynamic Programming. In this question :
1. You are given an array(arr) of positive integers of length N which represents the dimensions of N-1 matrices such that the ith matrix is of dimension arr[i-1] x arr[i].
2. You have to find the minimum number of multiplications needed to multiply the given chain of matrices.
To attempt and submit this question, click here: www.pepcoding....
For a better experience and more exercises, VISIT: www.pepcoding....
Have a look at our result: www.pepcoding....
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
perquisite for this problem is Palindrome partitioning problem and for Palindrome partitioning problem prereq. is Rod cutting problem, this series itself DP 😂😂🔥🔥, depend upon previous state
that palindrome partitioning also needs count of palindromic substring for that gap strategy matrix matrix too
😂
This video itself is prerequisite for ballon burst problem 😂.
I always prefer your videos over others' for the depth you cover. Great explanation sir once again!!
Awesome, thank you!
The explanation was great as always sir. I would recommend including a recursive approach too in the video. If in an interview we directly give DP solution the interviewer might think ki ratt liya hai bande ne.
then why he is asking a easily available question...xd... practice nahi karein kya......
These r trivial questions , hardly any interviewer ll ask
@@theuntoldtree Really 🤔
@@decostarkumar2562 yeah,same to nhi puchhega
@@theuntoldtree hello vro, good to see you here😂^_^
Gap strategy kaha par milegi
Thank you very much Sir. Best explanation. Bahut acha padhaate hai aap. You value your viewers.
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review - g.page/Pepcoding/review?rc
This series is underrated
Brust ballon problem solve krne k liye Matrix chain problem dekho ar Matrix chain problem ko solve krne k liya pallendromic cut wali video dekho ye ksa endless loop h😂😂
Hats off sir for such dedication towards teaching.
Wonderful explanation once again . Love the way you go in the very depth of every problem . Thanks a lot Sir !
please rearrange the playlist properly sir, I don't know where gap strategy is explained. Im watching video according to playlist. 🙏🏾🙏🏾🙏🏾🙏🏾
yes sir, please
Osm explanation 😍😍
as soon as i see your video i ignore others and click on it because you drill the concepts in the head
Sir bhut maza aa gaya . Awesome .
22/79 Done
Keep it up!
Sir, Maza aa gaya. Kya mast samjhate ho aap yaar. LITERAL GOD. I hope god bless you and your family. MAST VIDEO
subscribe bhi kr dia and bell notification bhi dba di. Great Content Sir Thank You very Much.
Thank you so much keep motivating, keep learning and keep loving Pepcoding😊
Maza aa gaya !! ❤️
Thank you 🙏🏼
Thanks a lot, Sir for this amazing explanation.
You are most welcome😊
Keep watching and keep learning🙏
Great sir burst balloon bhi post kijiye sir jldi . Aapse sikhna hai
hanji. ajkal mei dalega.
Hello sir, Kya aap abi sirf DP k questions complete karoge ya sath me parallel me aur koi topic b karoge ?
Agar ap koi aur topic parallel me karoge to uska nam bata dijiye taki wo dusre source se parh k time waste na karen ham,
Thank you so much for this awesome content.
Hashmap-Heaps parallel mei kar rha hun. Thank you for the kind words.
working sir, thanks for the great explaination .
Can someone please tell me what is the first video in which gap strategy is been taught?
For better experience, precised content you should visit - nados.pepcoding.com
✅ Signup to NADOS
✅ And boost your coding career
Diagonal traversal of an array
Very NIce Explanation
as usual "east or west sumeet sir is the best"
Keep learning, Keep growing and keep loving Pepcoding!😊
How did you decide you are going to use Gap Strategy, could you please also explain, where this one becomes different from Longest common subsequence, or how many other ways will be there to solve this problem.
yes please sumit sir
Where you see problem is kind of sub arrays like ab BC ABC bcd. Because the complete abcde is forming from all that sub parts which is present in gap strategy matrix.
sir ye questions ko yaad krna pdega kya , kyuki iska method kahi aur nhi lgta hai aur easy to visualise bhi nhi hai
Love ur explanations ...
Thanks a ton.
For better experience and well organised content sign up on nados.io
And for being updated follow us on Instagram instagram.com/pepcoding/
@@Pepcoding sure
is there solution for above with n² complexity
Sir pls ek baar iss ka recursive code bhi bata dijiye na..
Hanji beta, ek bari jo agenda main questions h vo complete kr le, then ye sb cheeze bhi cover kr lenge
Can it be solved in n2 time complexity as min cut palindrome question?
Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.
Great Video.
Just one thing, this solution is giving TLE in python on pepcoding.
18:45
Sir aap live kyu nhi aate ajkal ? (9pm wala)
10 video bnae bina sharam aati hai live ane mei
@@Pepcoding sir is there any way to be teaching assistant in pepcoding ,i have experience
Of 4 months at CN in C++ Data Strt.
Epic ❤️
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, will you like to review us here - g.page/Pepcoding/review?rc
Nice video
Thanks
After rod cutting one can easily solve this thanks sir
Yes 👍
❤️🔥💯
Sir, dp ma confidence nhi aa rha, abhi bhi koi naye question ko soch nhi pata dp ma. Foundation ke saare questions kre ha aur levelup ke bhi 30 questions kr chuka hu dp ke. Koi tip dijiye Sumit sir
Maths and memization
bhai common questions ko group krke revise krte rho ,agr ye 70-80 questions kaise bhi krke aate hia toh aage probability jyada hogi ki question ban jaega
sir, gap strategy ka video kaunsa hai
visit nados.pepcoding.com, post your doubts; there our community will help you out.
Million likes video this is
Thank you so much and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
hello sir aap at 19:20 par jo loop lagake bol rahe ho mai umeed karta hu aapko ata hoga uska explanation kaha mil sakta hai apne kisi previous video mae keya hai explain please it will be very helpfull and sir love your videos
Here you'll find the gap strategy - www.pepcoding.com/resources/data-structures-and-algorithms-in-java-levelup/dynamic-programming/lps-official/ojquestion.
Keep learning and keep growing😊
Sir i am facing problems that i can not convert my logics into code , so i can not solve any of your question without watching your videos but i understand logic quickly. help me sir.
Bhai ap glt jgh agya ye level up h, ap 4-5 baari foundation cover kijiye phir hojayega
@@anjneykumarsingh4461 mai foundation course hi kar rha hu ye letest video tha isliye ispr comment kiya
beta, thoda karte karte aaega. 200-300 question jis din kar doge firr nahi aaegi ye problem
@@Pepcoding thanks sir I will not losing hope. You hard work inspired me a lot.
nice
Thanks
Sir, DP kb tk complete ho jayegi??
25 din aur
Sir apjo samjha dete hai wo kathin bilkul bhi nhi lagta
maja aya
i swere no one cam ever match you in terms of explanation
//MATRIX CHAIN MULTIPLICATION(Strategy according to recursion example) + Memoization
import java.util.*;
public class Main{
//Size of the Array is upto 1000....
static int dp[][] = new int [1001][1001];
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int [n];
for(int i=0;i=j){
dp[i][j] = 0;
return 0;
}
else if (dp[i][j]!=-1) return dp[i][j];
else{
int minimum = Integer.MAX_VALUE;
for(int k=i;k
// Recursion + DP (Java)
import java.io.*;
import java.util.*;
public class Main {
static int dp[][]=new int[1002][1002];
public static int mcm(int[] arr){
return solve(arr, 1, arr.length-1);
}
public static int solve(int arr[], int i, int j)
{
if(i>=j){
return 0;
}
if(dp[i][j] != 0)
{
return dp[i][j];
}
int min = Integer.MAX_VALUE;
for(int k=i; k
22/79 Done
Well done