CODEWITHSUNDEEP
algorithmdynamic-programming
user1311286
user1311286

Reputation:

Matrix Chain Multiplication + Dynamic Programming + Recurrance Relation

I am going over my review worksheet and was looking for some help with finding the recurrence relation for chained matrix multiplication using dynamic programming.

The problem verbatim: Consider the optimal parenthesization problem for the chained matrix product M0M1…Mn - 1 with associated dimension sequence (d0, d1, … ,dn). Derive the recurrence relation on which the dynamic programming solution for this problem is based, i.e., a recurrence relation for the minimum number mij of multiplications over all parenthesizations of the chained product MiM1…Mj . Don’t forget the initial condition.

I understand the formula for M[i,j] (M[i,j] = M[i,k] + M[k+1,j] + pqr). This definitely has recursion. But how to I determine the recurrence relation? Is this not the recurrence relation already? Also what is mean by "associated dimension space"?

Upvotes: 0

Views: 5089

Answers (1)

Ravi Gupta
Ravi Gupta

Reputation: 6460

See section 6.5(Chain Matrix Multiplication) from http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf

Here by associated dimension he means that the dimension of each matrix i.e M0 has dimensions d0, M1 has d1, M2 has d2 .... so on.

Upvotes: 2

Related Questions