Reputation: 153
I'm now practice dynamic programming by myself. For the classic problem "matrix-chain multiplication" is to find the minimize number of scalar multiplication. Which is,
M[i,j] = 0 if i=j
= Min(i<=k<j){M[i,k-1]+M[k,j]+Pi-1*Pj*Pk}
and its time complexity is O(n^3)
But I'm just curious what if I want to find the "maximization"(instead of min) of scalar multiplication, does it exist a optimal structure and is it possible to solve it in polynomial time?
Upvotes: 2
Views: 1676
Reputation: 76381
The exact same reasoning as the minimization applies:
If you multiply a1 ... ai, the resulting matrix dimension does not rely on the internal parenthetization.
It follows that that if the optimal - that is, most expensive - partition of a1 ... ai ... an is to multiply the matrices from 1 to i and from i + 1 to n, then it is composed of the optimal solutions to a1 ... ai and ai + 1 ... an
Since the optimal substructure remains, you can use the same algorithm as minimization (of course, changing the criteria for optimality from minimum to maximum).
Upvotes: 3