Matrix Chain Multiplication Dynamic Programming

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

[@ashwinvarma9349]

I always prefer your videos over others' for the depth you cover. Great explanation sir once again!!

[@Pepcoding]

Awesome, thank you!

[@chandrakantshinde6]

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

[@mickyman753]

that palindrome partitioning also needs count of palindromic substring for that gap strategy matrix matrix too

[@karanveersingh5535]

😂

[@abhilashpatel6852]

This video itself is prerequisite for ballon burst problem 😂.

[@harshshukla7260]

Thank you very much Sir. Best explanation. Bahut acha padhaate hai aap. You value your viewers.

[@Pepcoding]

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

[@yashCeo]

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.

[@shubhamagarwal2998]

then why he is asking a easily available question...xd... practice nahi karein kya......

[@theuntoldtree]

These r trivial questions , hardly any interviewer ll ask

[@decostarkumar2562]

@@theuntoldtree Really 🤔

[@theuntoldtree]

@@decostarkumar2562 yeah,same to nhi puchhega

[@deeptimittal05]

@@theuntoldtree hello vro, good to see you here😂^_^

[@devkumar9889]

This series is underrated

[@asthagupta3813]

Gap strategy kaha par milegi

[@rakshitdevra7060]

Hats off sir for such dedication towards teaching.

[@DivyaPrakash-bj6zk]

Sir bhut maza aa gaya . Awesome .

[@aritralahiri8321]

Wonderful explanation once again . Love the way you go in the very depth of every problem . Thanks a lot Sir !

[@karthikrashinkar204]

please rearrange the playlist properly sir, I don't know where gap strategy is explained. Im watching video according to playlist. 🙏🏾🙏🏾🙏🏾🙏🏾

[@codelikepro1088]

yes sir, please

[@ashutak]

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.

[@gouravgoel2974]

yes please sumit sir

[@jatinlodhi980]

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.

[@ankushmilan6167]

Can someone please tell me what is the first video in which gap strategy is been taught?

[@Pepcoding]

For better experience, precised content you should visit - nados.pepcoding.com ✅ Signup to NADOS ✅ And boost your coding career

[@amanshrivansh2847]

Diagonal traversal of an array

[@mdnazirhusain1721]

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😂😂

[@umangbehl8152]

as soon as i see your video i ignore others and click on it because you drill the concepts in the head

[@hritikanand9734]

Osm explanation 😍😍

[@mickyman753]

sir ye questions ko yaad krna pdega kya , kyuki iska method kahi aur nhi lgta hai aur easy to visualise bhi nhi hai

[@ArcGaming07YT]

is there solution for above with n² complexity

[@deeksha6514]

Thanks a lot, Sir for this amazing explanation.

[@Pepcoding]

You are most welcome😊 Keep watching and keep learning🙏

[@rohandevaki4349]

working sir, thanks for the great explaination .

[@shivammehta9661]

Very NIce Explanation

[@nknidhi321]

Maza aa gaya !! ❤️ Thank you 🙏🏼

[@kirtimaangogna8468]

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.

[@Pepcoding]

Hashmap-Heaps parallel mei kar rha hun. Thank you for the kind words.

[@HappyHappy-ih5zp]

subscribe bhi kr dia and bell notification bhi dba di. Great Content Sir Thank You very Much.

[@Pepcoding]

Thank you so much keep motivating, keep learning and keep loving Pepcoding😊

[@schwarzenneger9240]

Sir aap live kyu nhi aate ajkal ? (9pm wala)

[@Pepcoding]

10 video bnae bina sharam aati hai live ane mei

[@sauravsharma4615]

@@Pepcoding sir is there any way to be teaching assistant in pepcoding ,i have experience

[@sauravsharma4615]

Of 4 months at CN in C++ Data Strt.

[@ZentrexGaming]

Sir, Maza aa gaya. Kya mast samjhate ho aap yaar. LITERAL GOD. I hope god bless you and your family. MAST VIDEO

[@nehasht2]

Love ur explanations ...

[@Pepcoding]

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/

[@nehasht2]

@@Pepcoding sure

[@optimizer_____2420]

Can it be solved in n2 time complexity as min cut palindrome question?

[@Pepcoding]

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.

[@priyanshukhullar5836]

Great sir burst balloon bhi post kijiye sir jldi . Aapse sikhna hai

[@Pepcoding]

hanji. ajkal mei dalega.

[@nehaagrawal177]

sir, gap strategy ka video kaunsa hai

[@Pepcoding]

visit nados.pepcoding.com, post your doubts; there our community will help you out.

[@manishkumarsingh4631]

22/79 Done

[@Pepcoding]

Keep it up!

[@factswithai2]

as usual "east or west sumeet sir is the best"

[@Pepcoding]

Keep learning, Keep growing and keep loving Pepcoding!😊

[@anurag4316]

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

[@Pepcoding]

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😊

[@devanshubilthare5277]

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

[@anjneysingh2090]

Maths and memization

[@mickyman753]

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

[@princypareek2992]

Sir pls ek baar iss ka recursive code bhi bata dijiye na..

[@Pepcoding]

Hanji beta, ek bari jo agenda main questions h vo complete kr le, then ye sb cheeze bhi cover kr lenge

[@kushagrashekhawat8227]

Sir, DP kb tk complete ho jayegi??

[@Pepcoding]

25 din aur

[@NeerajSharma-mz4es]

After rod cutting one can easily solve this thanks sir

[@Pepcoding]

Yes 👍

[@mukeshojha9318]

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.

[@anjneykumarsingh4461]

Bhai ap glt jgh agya ye level up h, ap 4-5 baari foundation cover kijiye phir hojayega

[@mukeshojha9318]

@@anjneykumarsingh4461 mai foundation course hi kar rha hu ye letest video tha isliye ispr comment kiya

[@Pepcoding]

beta, thoda karte karte aaega. 200-300 question jis din kar doge firr nahi aaegi ye problem

[@mukeshojha9318]

@@Pepcoding thanks sir I will not losing hope. You hard work inspired me a lot.

[@kunjpatel1703]

Great Video. Just one thing, this solution is giving TLE in python on pepcoding.

[@twicein14days]

18:45

[@rahulbhatia3075]

Nice video

[@Pepcoding]

Thanks

[@payalsagar1808]

Epic ❤️

[@Pepcoding]

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

[@ashirwadshukla8221]

Million likes video this is

[@Pepcoding]

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 )

[@dipuprasad9196]

Sir apjo samjha dete hai wo kathin bilkul bhi nhi lagta

[@b.sainathreddy4567]

nice

[@Pepcoding]

Thanks

[@karanveersingh5535]

❤️🔥💯

[@cyberpolice3183]

maja aya

[@viditvaish7317]

i swere no one cam ever match you in terms of explanation

[@ayushmansharma5321]

//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

[@technicalrobot9685]

// 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

[@manishkumarsingh4631]

22/79 Done

[@Pepcoding]

Well done