CODEWITHSUNDEEP
algorithmdynamic-programming
Pwan
Pwan

Reputation: 153

Dynamic Programming - "maximize" matrix chain multiplication

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

Answers (1)

Ami Tavory
Ami Tavory

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

Related Questions