I want to develop an algorithm which finds the optimal sequence of multiplications to multiply n matrices. For example, if we have:
M1 x M2 x M3 x M4 x M5 x Mn
The algorithm should place the optimal parenthesis to reduce overall number of scalar multiplications. For example, a possible output may be:
(M1 x M2) x (M3 x M4 x (M5 x Mn))
I realize we can place the parenthesis after finding an order for all of the multiplication (x) operators to operate in.
There is certainly a cost associated with each multiplication:
Cost (M1,M2) = rows(M1) x columns(M1) or rows(M2) x columns(M2)
At each step, if we find the subproblem associated with each (x) operator. For example, at the first step, we have:
OPT(do M1 x M2 first)
OPT(do M2 x M3 first)
OPT(do M3 x M4 first)
OPT(do M4 x M5 first)
OPT(do M5 x Mn first)
The problem is, that the number of OPTimal subproblems is not a fixed number. Normally, in a dynamic programming algorithm, we have a fixed number of OPT operations of which we take min or max of.
Is it valid to take n (variable number of) OPT operations in a dynamic programming algorithm?
P.S. I realize another feature of dynamic programming algorithms is the ability to memoize. We can certainly memoize since we will have repeated subproblems through different paths. For example, the following set of parenthesis can be approached through two different paths:
(M1 x M2) x (M3 x M4) x M5 x Mn
- Do M1 x M2 first then do M3 x M4
- Do M3 x M4 first then do M1 x M2