*Example for Dynamic Programming. *

**EXAMPLE E5.6-1 : ****Best way to multiply arrays. **

**L**ets assume that we must calculate the result of:**A:=A****1*****A****2*****....*A****n**,where Ai is an array
whose dimension are **d****(i-1)****Xd****(i)****.**We must say that this problem and the way to solve it is
obviously similar to the problem of the minimum routes in paragraph **P5.7**.To make the problem
simpler,we say that if the M array is *pXq* and the N array is *qXr** *in dimensions then the cost
calculating the product M*N is *a*p*q*r* and *a* is independent from the p,q,r.

The multiplication of the arrays can be done in numerous of ways.If for example n=4 then **A=A****1****
(A****2 ****(A****3****A****4****) )** or **A=( (A****1****A****2****) (A****3****A****4****) )** etc.There can be easily made examples,where there are
great differences in the calculation cost,for every different way.Therefore the way of calculation
with the minimum costs is asked,without having to find the cost for every solution itself.

Let there be:

**G****(i,j)****:=A****(i)****,,A****(j)**** , j>=i **

What we are interested in is the array *G**(1,n)**=A*.Let's call **e(****G****(i,j)****)** the minimum calculation cost
for the G(i,j) array.If j=i,no calculation is needed,that is* ***e(****G****(i,j)****)=0 for i=1,..,n** . If j>i we can see
that no matter how we will calculate the G(i,j) array,at the last step the multiplication of 2 other
arrays will be needed.Every one of those arrays,will consist a sub-product,that is:

**G****(i,j)****:=G****(i,k)****G****(k+1,j)**** i<>j**

Therefore

**e(G****(i,j)****)=min {e(G****(i,k)****) + e(G****(k+1,j)****) + a*d****(i-1)*****d****(k)*****d****(j)**** } and i<=k<j **

We notice that the differences **k-i **and **j-k** can not grow bigger then the** j-i **difference. This
means that the formula above can be considered as a retroactive formula,where the calculation
of the e(G(i,j) is made by the difference of the pointers order.The initial conditions
are:e(G(i,j))=0.That means that we start with the calculation of the minimums e(G(i,i+1)) and go
on like this,or in other words calculate the elements of the upper triangular array which contains
the e(G(i,j)), j>i in diagonals.This array holds the role of storing,and the (5.6-1) formula
obviously rejects many of the choices among all the possible ways to calculate the G(i,j)
chooses the minimum one,so that it can be used in the calculation of the e(G(i,j)).In this way we
understand that both main characteristics a and b of D.P. are satisfied.Finally it is quite easy to
show that our algorithm has a total cost of O(n^{3}),despite the presence of exponential number of
possible solutions.

HTML PAGE DIRECTOR :Papaioannou Panagiotis