Matrix Chain Multiplication Concept Doubt

#1

Why in this problem, we need to take
row index<=column index?

#2

hello @Kinjal

we only need half of matrix to store results. so if we want to store in upper half we should fill in grid satisfying row index <= col index.

but if we want to store in lower half then we need to fill cell that satisfy row >= col
its totally implementation thing nothing related to solution logic.
btw i will suggest to first solve it using top down

1 Like
#3

Why we need only half of the matrix to store results?

#4

solution of portion [i…j] will be same as solution for [j…i] right?
we are considering same problem right?
so out of N^2 pairs , each problem is considered twice
thats why only N^2/2 array is required to store all answers

#5

Yeah. dp[1][2]=dp[2][1]

#6

Recurrence relation,
dp[x][y]=min(dp[x][k] + dp[k+1][y] + a[x]*a[k+1]*a[y+1] where k=>[x,y-1]

why k values goes upto (y-1) only, why not upto y?

#7

bro ?
solve(i,j) = solve(i,j) // dont u think u will call on same problem again n again which will put u in infinite loop

#8

Yeah I got it. So we only compute for half of the matrix to get the solution. But, infinite loop…How?? It will take O(n^2) if we consider overlapping subproblems like a new problem…

Why?

#9

put k=y , u will get it

#10

Yeah, if we do k=y then we violate the condition, r<=c

#11

yeah , u can thing in that way as well

#12

Bhaiya, I want to understand it in your way…and what I have said was just a mathematical proof…

#13

consider this small example ->
sum(n) = 1+sum(n-1) right?

#14

okay…

#15

if i say
sum(n) =sum(n) this is true , but dont u think , u r stuck in infinite loop. u r calling on same problem again n again instead of breaking it in subproblem.

same is the the case when u r saying why not k==y.
if k==y then
dp(x,y) -> dp(x,y) // beda garg :joy::joy:

#16

Bhaiya, what I was asking that why the range of k=>[x,y-1],
what if the range of k=>[x,y]

#17

i m also explanning same bro.
if k=y
dp[x][y]=min(dp[x][y] + dp[k+1][y] + a[x]*a[y+1]*a[y+1] )

did u see something .
dp[x][y] is depending on itself ( is it logical)

1 Like
#18

Acchhha…got it bhaiya.
dp[x][y]=dp[x][y]+… if k=y

#19

In this relation, a[x]*a[k+1]*a[y+1] is the cost of two subarray with (row,col) : (x,k) and (k+1,y)
But, here column size of first array and row size of second array are not same then how can we find the cost?

What we know that, if we want to find the cost of two matrices with (row,col) :
(r1,c1) & (c1,c2)
Cost will be => r1*c1*c2

#20

matrix multiplication will always hold.

{10, 20, 30, 40, 30}
There are 4 matrices of dimensions 10x20, 20x30, 30x40 and 40x30.
doesnt matter how u add brackets u will always be able perform multiplication

1 Like