Another way to think of this problem (Matrix-chain multiplication)

  • 1

    If you think of bursting a balloon as multiplying two adjacent matrices, then this problem is exactly the classical DP problem Matrix-chain multiplication found in section 15.2 in the book Introduction to Algorithms (2nd edition).

    For example, given [3,5,8] and bursting 5, the number of coins you get is the number of scalar multiplications you need to do to multiply two matrices A[3*5] and B[5*8]. So in this example, the original problem is actually the same as given a matrix chain A[1*3]*B[3*5]*C[5*8]*D[8*1], fully parenthesize it so that the total number of scalar multiplications is maximized, although the orignal matrix-chain multiplication problem in the book asks to minimize it. Then you can see it clearly as a classical DP problem.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.