35 Matrix chain multiplication Memoization

[@qR7pK9sJ2t]

Plzz watch from 12:00 if u know already know the concepts of why we use bottom up DP

[@akshaydeshpande127]

You mean memoization (top down)?

[@vikasjoshi7236]

thnx

[@lone_wolf7721]

Hamlog pura dekhenge taki ... Aditya bhaiya ka views time badh sake .... Jiise unko bhi kuch fyada ho ... Itna to kar hi sakte hai

[@SHASHANKRUSTAGII]

class Solution { public: int dp[1001][1001]; int matrixChainMemoised(int p[], int i, int j) { if (i==j) return 0; if (dp[i][j]!=-1) return dp[i][j]; dp[i][j] = INT_MAX; for (int k = i; k < j; k++) { dp[i][j] = min(dp[i][j] , matrixChainMemoised(p, i, k) + matrixChainMemoised(p, k + 1, j) + p[i-1]*p[k]*p[j]); } return dp[i][j]; } int matrixMultiplication(int n, int p[]) { memset(dp, -1, sizeof dp); return matrixChainMemoised(p,1,n-1); } };

[@vanisameera9439]

Thank you

[@xsuritox1058]

for someone having problem with the audio issues, close your eyes and remember how he solved the previous problems, everything will get sorted out.....✌

[@TheAdityaVerma]

✌️✌️❤️❤️

[@PiyushCodes-ph3hl]

@@TheAdityaVerma please complete this playlist and other playlist also coz u are the only one whos explaination i can understand

[@ananyakashyap4887]

Dusre dp playlists 1x pe dekthi thi..phir bhi samaj nahi aata tha.. Aapka Playlist to 2x mein Dekh rahi huin...phir bhi concept ache se samaj aa raha hein... Thank You for making me fell in love with DP ❤❤

[@namangupta2587]

bhai seriously you deserve almost a million subscribers.....mind blowing explanantion

[@TheAdityaVerma]

I am glad you feel that way brother !! You can help this channel grow, please share where ever you can with your reviews !! That would be a great help.

[@namangupta2587]

@@TheAdityaVerma sure bro....i bet none other channel can explain better than you😍😍

[@0anant0]

34 of 50 (68%) done! Nice revision of memoization.

[@richa6695]

@Aditya, would really appreciate it if you can discuss the time and space complexity of your solutions too :) Great videos though! keep up the good work!

[@manusoni4737]

TC = O(n^2) or O(m*n) SC = O(n^2) or O(m*n) Wherever u find a table!!

[@sundramsharan1256]

@@manusoni4737 You are wrong!! The time complexity here is O(n^3). There is a loop inside the recursive function. Happy Coding ;)

[@KRISHNAKUMAR-yk3tt]

ajit dobhal apke relative hai kya? ;-)

[@dakshdagariya2692]

@@KRISHNAKUMAR-yk3tt kuch bhi bolega

[@KRISHNAKUMAR-yk3tt]

@@dakshdagariya2692 teri kyu jali ?

[@soumensinha305]

Best Ever explanation. Your teaching methodology is the impeccable

[@vaibhavsharda9443]

Don't get confused between top-down and bottom-up. Always remember them as Memoization(Top Down) and Tabulation (Bottom Up) Dynamic Programming Methods. The intent here is clear though!!

[@theuntoldtree]

Doesn't matter too

[@rituraj6056]

I'm going to complete ur playlist on dp in just 3 days bcz u made it too easy. THANKS!

[@piroboi8830]

@@Ayush_. ho jaati h 3 din m but practice krni pdegi bht zyada saath saath

[@SherubThakur]

I saw a bunch of solutions in python on this video Looking at them I thought I bet this can be done way more concisely than this. So here is how you can do this. def mcm(arr: List[int]) -> int: @cache def mcm(i: int, j: int) -> int: return min((mcm(i, k) + arr[i] * arr[k] * arr[j] + mcm(k, j) for k in range(i + 1, j)), default=0) return mcm(0, len(arr) - 1) This is pretty much it. This is all you need to solve this question with memoization. `@cache` is all you need to solve all the dp questions. Just write the basic recursive version stick a `@cache` and you are done. Moreover it is also super simple to create this decorator.

[@Miniisisters]

Ye bnda kitna awesome h yr 🥺♥️🙏

[@g1patil]

For someone who still wants to simplify. ex : function myFunction( int parameter1 , int paramater2) = answer What you do is just save it. memoization[ paramater1][ parameter2] = answer ; Also the way to identify the size of memory array is : memoization[ max value of parameter1 + 1 ] [ max value of parameter2 + 1 ]

[@vineetdubey2391]

For memoization, the table dimensions should be dependant on the maximum index "i" and not on the maximum value of arr[i]. Hence, for a given array arr[] of length N The memoization table should be initialized as (in Java): int[][] t = new int[N][N];

[@tanaykamath1415]

yes!

[@avadhoot05]

Dont know about java. but in most of the compiled languages, array size should not be a variable. Reason: Compiler must be aware of the size to allocate memory at compile time but the variable is assigned at run time. that's why he initialized the array with a constant value.

[@abrahamlincoln5724]

@@avadhoot05 Are you saying that a matrix of size N x N is a variable sized array?

[@Abhisheky418]

I really hope god gives me enough so that i can return you what you gave me and many more like me for free of cost. hope u get 1 million and more. thanks again

[@supermadhujya1]

bro...everythings good and all but bottom-up method is the method where we use table and loops. The memoized solution is actually called top-down. this has been bugging me from video no. 1, but yeah just wanted to mention it

[@TheAdityaVerma]

Yeah I did mention it in the comments like 3 times now, What I wanted to do was memoization and tabulation and I hope there is no difficulty in understanding my intent. Thanks !

[@PatelFromPatna]

@@TheAdityaVerma sir for all the concepts you explain memoization and top down...does that mean the memoization explained by you is bottom up approach?

[@devanshrastogi6305]

@@PatelFromPatna memoization and top down are same thing, similarly tabulation and bottom up are same.

[@PatelFromPatna]

@@devanshrastogi6305 but in the video memoization is termed as bottom up nd second approach is top down which is shown different from memoization

[@devanshrastogi6305]

@@PatelFromPatna yes he made a mistake in naming them, he also admitted to it in comment section of multiple previous videos of the playlist.

[@thelegend5248]

Bro.. what microphone, camera and stick u use to keep in such position can you say? It's nice and interesting!! 😇

[@dakshdagariya2692]

gopro

[@_ADITITARATE]

Please make a playlist on graph and backtracking.

[@ngtv5608]

Bro please make a series on GRAPH !!

[@gauravraj2604]

Although I already knew the logic for top-down approach after watching the recursion video, I literally watched this complete video (at 1.5x speed) with a fear "kya pta kuch naya concept sikhne ko mil jaaye".. Thanks a lot

[@shashankgaikwad1043]

Code in Python: import sys t = [[-1 for i in range(10)] for i in range(10)] def mcm(arr,i,j): if(i>=j): return 0 if(t[i][j]!=-1): return t[i][j] mn = sys.maxsize for k in range(i,j): temp = mcm(arr,i,k)+mcm(arr,k+1,j)+(arr[i-1]*arr[k]*arr[j]) if temp

[@derilraju2106]

class Solution: def matrixMultiplication(self, N, arr): cache = {} def dfs(arr,i,j): if i>=j: return 0 if (i,j) in cache: return cache[(i,j)] _min = float("inf") for k in range(i,j): temp = dfs(arr,i,k) + dfs(arr,k+1,j) + arr[i-1]*arr[k]*arr[j] _min=min(_min,temp) cache[(i,j)] = _min return _min return dfs(arr,1,N-1)

[@sankalparora9374]

Thanks for pointing out to skip to the end for the code changes.

[@suviyashraj]

Object Oriented Python Code: - class MCM: def __init__(self,n) -> None: self.dp = [[float('inf')]*n for i in range(n)] def recursive_mcm(self, arr, start, end): if start >= end: return 0 mn = float('inf') for k in range(start,end): res = self.recursive_mcm(arr,start,k) + self.recursive_mcm(arr,k+1,end) + (arr[start-1] * arr[k] * arr[end]) mn = min(mn,res) return mn def memoized_mcm(self, arr, start, end): if start >= end: return 0 if self.dp[start][end] != float('inf'): return self.dp[start][end] for k in range(start,end): res = self.recursive_mcm(arr,start,k) + self.recursive_mcm(arr,k+1,end) + (arr[start-1] * arr[k] * arr[end]) self.dp[start][end] = min(self.dp[start][end],res) return self.dp[start][end] if __name__ == '__main__': arr = [10,30,5,60] mcm = MCM(len(arr)) print("Matrix Chain Multiplication Cost: ", mcm.recursive_mcm(arr,1,len(arr)-1)) print("Matrix Chain Multiplication Cost: ", mcm.memoized_mcm(arr,1,len(arr)-1))

[@PiyushCodes-ph3hl]

Bhaiya Please DP series complete kardo and baki bhi karo apka explaination bohot achhe se samajh ata hai please @Aditya Verma

[@manish041000]

Memoized Dp is called Top down and the Other method where we build the solution using smaller subproblems is called Bottom Up. Looks like the author is confused here

[@jayshree7574]

Hey aditya, please make a video on edit distance, not even a single video on youtube is interesting enough, it's really confusing. It is a highly popular question and I really want it to learn it from you.

[@aayush5474]

check back 2back swe

[@LegitGamer2345]

lcs ka hi tho variation hai

[@fane1159]

this problem is giving tle while solving using hashmap , so try using the top down table approach , that will definitely work

[@knittingclub415]

Please @aditya graph & trees dono par video bana do plz !! Placement shuru hone wale but nhi padha ja raha

[@parambharti7095]

Awesome!!! Thanks Aditya.

[@charan775]

video for printing MCM?

[@tm2k23]

I was also searching for same 😂

[@siddhantagarwal4941]

Video is lagging. Voice is coming before and video is coming later.

[@lifeNfreek]

why the first solve array we're passing same i and k value, don't you thkink both the mattrix have same value?

[@creativeengineer832]

Dp was my biggest nightmare but now it's my favourite.........

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@kumarkanhaiya376]

Bro..what an excellent explanation, I love your videos and I am definitely gonna share it with my friends, I had a doubt people say top down approach is slower than bottom up approach as there is recursion involved in it, can you tell me what would be the time complexity of the above code you explained and is it slower than tabulation approach?

[@TheAdityaVerma]

It has a same order complexity as tabulation (if tabulation is order of n it will be too, maybe slower by a constant factor) and NO, its not always slower, it really depends upon the problems, on how it gonna be as compared to tabulation. It might be slower (often this is the case) and it can be faster too (this can happen too). All that depends upon the number of sub-problems and how they are distibuted in the recurisve tree. If all subproblems must be solved at least once, a bottom-up dynamic-programming algorithm usually outperforms a top-down memoized algorithm by a constant factor No overhead for recursion and less overhead for maintaining table There are some problems for which the regular pattern of table accesses in the dynamic-programming algorithm can be exploited to reduce the time or space requirements even further If some subproblems in the subproblem space need not be solved at all, the memoized solution has the advantage of solving only those subproblems that are definitely required. Hope thats clears your doubt.

[@kumarkanhaiya376]

Thanks a lot, that clears my doubt awesome explanation 😄♥️

[@TheAdityaVerma]

Do support the channel grow by sharing it. Thanks for Watching !!

[@lovleshbhatt7797]

I think aditya bhaiya saying opposite, I mean bottom up dp is using creation of dp table and he said it is Top down dp and similiarly memorization with recursion is actually top down dp but bhaiya says it is bottom up dp.. So Aditya bhaiya I think there is some missunderstaing

[@suhasnayak4704]

Good explanation, small correction: Memoization = Top Down not Bottom Up

[@tanujk1465]

memoization is bottom up not top down....you should correct yourself and think 100 times before posting wrong information

[@yashpawar4296]

@@tanujk1465 lol 🤣

[@84y87]

@@tanujk1465 Are you sure about that ? As far as I know, memorization is the top down approach and tabulation is the bottom up.

[@naveennayak8365]

​@@tanujk1465Memoization follows top-down approach to solving the problem. It consists of recursion and caching.

[@ganavijayaram7987]

@TheAdityaVerma , still waiting for LIS, fibo and Kadane's videos

[@shubhamtiwari7704]

can anyone explain why size of t[size+1][size+1] i am confused for " i " row value.

[@mayur_madhwani03]

video dekhte dekhte ad me trailer aa gaya movie ka vo bhi dekh liya padhai aur entertainment dono yahin mil gaye 😂😂

[@suyashjaiswal3238]

Where is the Tabulation method Video??

[@PushpendraKushvaha]

At 12:22 anyone who knows why he declare 2D array with size 1001?

[@raunaksingh8913]

that's the general size of input for questions like this so he's already defining a global 2D array that can work for all problems.

[@amanpreetsinghsetia1524]

Last mein return kya karna hai ?

[@nityanandbhaskar2155]

delay audio by 12 sec to make it perfect. nice video anyways

[@herculean6748]

In MCM, I took int static dp then I got compiler error, but when I took int dp it was running, why is that???

[@iamseeker-99]

Tabulation: Bottom Up. Memoization: Top Down.

[@bhavyapandey]

Bhaiya placements start hone wale hain, please graph par bhi ek series bana dijiye🙏🏻 Usko khud se bilkul nahi padha ja raha

[@christianoronaldo1662]

kon sa college yar ?

[@shouvikdutta2825]

declaring table in globally, will give u advantage of the problem where for a particular test case value the value remain constant like egg dropping problem, here value of dp[i][j] change with different test cases with the give array. So it will return wrong answer most of the times. Otherwise we have to memset it with each function call. Kindly reply, if I am wrong.

[@TopLists178]

Code time limit exceeded. Only 6/127 test cases are passing. Any optimised solution ?

[@sutirthosen]

Thanks for providing awesome content! Can you please teach the iterative version as well?

[@adityagirishpawate1465]

the problem with your videos is that its too good. No one would like to share such good content. That's why your channel has not grown so much. Otherwise you should have atleast 100k subs by now.

[@sanjayvasnani988]

Sad but True. To everyone watching, If you don't want to share with your friends, at least share with your juniors. This channel deserves much more recognition.

[@karanveersingh5535]

@@sanjayvasnani988 👍

[@035-harshitsingh7]

@@sanjayvasnani988 Yeah even i think the same😅😅😅😅

[@yashagrawal1663]

How come in the last you said its a bottom up approach

[@hemang10]

Great video! But in this video I am noticing a lag in the audio and video and not a proper sync. It'd be really great if you can fix this, just by delaying the audio 2-3 seconds.

[@PiyushKumar-ix9jp]

sir what to do if we have to print the parenthesis string which shows how to do the optimal multiplication

[@SHASHANKRUSTAGII]

use stack.

[@vaishnaviagarwal5259]

please provide more videos on dp and also do discuss its tabulation method .

[@devsimplified1686]

I think aditya bhaiya saying opposite, I mean bottom up dp is using creation of dp table and he said it is Top down dp and similiarly memorization with recursion is actually top down dp but bhaiya says it is bottom up dp.. So Aditya bhaiya I think there is some missunderstaing

[@sakshamsengar9798]

can we fill the matrix by top down method ??????????????????????????????????????/can u guide me how to do that

[@pratikjha2742]

Please tell me how can any two cases overlap in this question, i think there will never be any overlap, so using memoization will not make any difference, please someone correct if i am wrong

[@vibezzzzz1820]

1:30 bhaiya recursion me catch masala daala pr dp nhi bni

[@anjana1700]

Sir, in memoization, shouldn't solve(arr,i,k) and solve(arr,k+1,j) be checked, if they already exist in the table, as doing in partitioning pallindrome case? Kindly correct me.

[@aayush5474]

i was wondering the same thing but if you observe carefully its is actually happening because of recursion!

[@Bdixit]

Basically we aren't checking inside for loop. But when solve(arr,i,k) will be called then it will itself be a new function call which will be first checking if ans of this solve is already there in dp table, and if it's there then simple one if will be executed and we will return back without furthur processing.

[@amanbhatt1087]

Audio lag sirf mujhe hi hoo raha hain ya video m hi synchronization nahi hain?

[@smitmodi9067]

memoization is top-down approach

[@saumyasharma9993]

K bhi toh change ho raha hai, uska kya?

[@balipavankalyan5008]

I hope ur subscribers will grow like anything like Covid-19 +ve cses :):):)

[@TheAdityaVerma]

Wow !! IDK how to react on that one 🤔🤔😂😂😂

[@classcure9769]

What if covid 19 patient decrease😬😆

[@balipavankalyan5008]

@@classcure9769 Again he'll raise like another virus!

[@anchalmishra2322]

All good bt why 2d matrix ???

[@mohammedsamir6846]

isnt it topdown approach???

[@ankurgupta4696]

what would be the time complexity of mcm 🤔🤔🤔

[@sundramsharan1256]

It's O(n^3). Happy Coding ;)

[@abhijitbarik6669]

e to memoization hai.but bar bar video mai bottom up dp kuy bol raha hai? memoization ko bottom up dp bolte kiya

[@disunique6107]

Nhi top down ...

[@gopalsingh-uc3bx]

bhaiya dp on grids k videos ayenge?

[@hemantsood9579]

BHai plz post video on top down approach as well

[@gregbiju1279]

Code for memoization java: class Solution{ static int matrixMultiplication(int N, int arr[]) { int[][] memoTable = new int[N+1][N+1]; for(int i=0;i

[@shubhi2648]

Till now we were also arriving at an iterative solution of a problem.. you probably missed that Aditya here

[@bite091_jamee7]

Dont know How to Thank YOu man

[@abhisheksrivastava5209]

bhai last mai mess up kr diye..clearly nhi likhe...btw nice explanantion

[@breakinggood-r2v]

Dp code?

[@gauravshukla5203]

can anyone provide production ready code for it?

[@samwaadvivaad8607]

bhaiya etna asaaan bna diya hai memoization kia hae bolu

[@derilraju2106]

Python class Solution: def matrixMultiplication(self, N, arr): cache = {} def dfs(arr,i,j): if i>=j: return 0 if (i,j) in cache: return cache[(i,j)] _min = float("inf") for k in range(i,j): temp = dfs(arr,i,k) + dfs(arr,k+1,j) + arr[i-1]*arr[k]*arr[j] _min=min(_min,temp) cache[(i,j)] = _min return _min return dfs(arr,1,N-1)

[@nishantgupta6902]

code: class Solution{ public: int t[101][101]; int solve(int arr[], int i, int j){ if(i>=j){ return 0; } if(t[i][j] !=-1){ return t[i][j]; } int mn = INT_MAX; for(int k =i; k tempans){ mn = tempans; } } return t[i][j] = mn; } int matrixMultiplication(int N, int arr[]) { // code here memset(t, -1, sizeof(t)); return solve(arr, 1, N-1); } };

[@balipavankalyan5008]

#python programming #Matrix chain multiplication(Memoization): import sys a=[40,20,30,10,30] n=len(a) i=1 j=n-1 dp=[[-1 for x in range(n)]for y in range(n)] def mcm(a,i,j): if i>=j: return 0 if dp[i][j]!=-1: return dp[i][j] 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

[@kunalkumarbarman9610]

Please make vidio on LIS.

[@raunak1786]

hope u got it

[@shauryarastogi6800]

what is the time complexity ?

[@blazecoder767]

I think it's O(n^3)

[@atreyadyaram850]

@@blazecoder767 can you please explain how?

[@lm3x10gjb6]

But what if n is at max 10^5

[@factgyankosh1370]

I Think their is k< j-1 in loop instead of k

[@m.e.t.a.l3125]

k

[@surathsrivastva6727]

Aditya bhai looop k bahar tmne t[i][j]=mn kiya h, Ye valo btt ekdm samjh nhi aaayi ? kon si value return ho rhi h kuch clear nhi hua

[@akashpwl]

are jo value calculate hui h usko table me dalna to hoha naa

[@pruthvirajk6019]

Bro Ur 🔥🔥🔥

[@ayushthakur733]

What a guy man ❤️

[@architguleria989]

Brother this is top-down approach and not bottom up. In bottom-up we start with the smallest problem and eventually arrive at the bigger original problem.

[@rishabhshukla9]

Ni chl rha ye code

[@surathsrivastva6727]

ANyone provide accepted solution ?

[@ShivamKumar-cv7jv]

code in c++ #include using namespace std; int mat[100][100]; int matrix_chain(int a[],int i,int j) { if(i>=j) return 0; if(mat[i][j]!=-1) return mat[i][j]; int mx=100000; for(int k=i;k

[@Muhammadmiad0.2]

14:34

[@bumblebee1078]

great explaination just try to give the working code in the commentss

[@bumblebee1078]

comments*

[@ShivamKumar-cv7jv]

#include using namespace std; int mat[100][100]; int matrix_chain(int a[],int i,int j) { if(i>=j) return 0; if(mat[i][j]!=-1) return mat[i][j]; int mx=100000; for(int k=i;k

[@prateekverma9166]

Anyone written this code in java ???? send link please. If coded on leetcode problem 312, it will be awsm

[@saurabhmarpadge7498]

Tabulation & Memorization Approach Code ide.geeksforgeeks.org/2FfB3N2foO

[@LegitGamer2345]

java code for MCM as close as possible to what god aditya has explained class Solution{ static int matrixMultiplication(int N, int arr[]) { int dp[][] = new int[N][N]; for(int i =0;i=j){ return 0; } if(dp[i][j]!=-1) return dp[i][j]; int min = Integer.MAX_VALUE; for(int k = i;k

[@amitpatil9258]

Thanks bhai....

[@NewBIE-xz5jm]

He just did top down approach is there any way for bottom up of this problem! my java code with memoization ! and ac! class Solution{ static int matrixMultiplication(int N, int arr[]) { int[][] dp=new int[arr.length+1][arr.length+1]; for(int[] ar:dp){ Arrays.fill(ar,Integer.MAX_VALUE); } int i=0; int j=arr.length-1; int ans=helper(arr,1,j,dp); return ans; //i code here } public static int helper(int []arr,int i,int j,int[][]dp){ if(i>=j){ return 0; }if(dp[i][j]!=Integer.MAX_VALUE){ return dp[i][j]; } for(int k=i;k

[@ayushvishwakarma4350]

Video and audio are not in sync I guess.

[@jp-wi8xr]

What is time complexity?!!! Memoization is top-down, NOT bottom up!

[@oqant0424]

thank u so much

[@tanishkumar6682]

understood

[@gregbiju1279]

Cdoe for tabualtion/bottom up: import java.io.*; import java.util.*; //User function Template for Java class Solution{ static int matrixMultiplication(int N, int arr[]) { int[][] dpTable = new int[N][N]; return solveByDP(arr,dpTable); } static int solveByDP(int arr[],int[][] dpTable) { int N=arr.length; for(int i=0;i=j is the base case of memoization dpTable[i][j] = 0; } } for(int i=N-1;i>=1;i--) { for(int j=i+1;j