I was trying to solve <https://www.spoj.com/problems/LISA/>

In the problem, the expression is given which has only \* and +. Placing bracket maximum value need to output.

like 

```
 1+2*3+4*5 = (1+2)*(3+4)*5 = 105

 2*0*3+7+1*0*3 = 2*((0*3+7+1*0)*3) = 42

```

The implementation of 2D dynamic problem way of solving I came across is like below. Taking each number is matrix row and column and doing bottom to top approach.

```
f(ci,cj) = Max( f(i,j-1) operator c(i,j) , f( i+1,j-1) operator c(i,i) )

Like 3,5 =  Max of [  (3,4) * (5,5) or (3,3)+(4,5) ]
         =  Max of [   7*5  or 3+20 ] 
         =  Max of [ 35,23 ] = 35

```

I am not able to prove that the result I am getting is maximum and correct. How to prove below solution is max and optimal?

```
-----------------------------------
      C1   C2   C3   C4    C5
C1     1    3    9   13    105
C2          2    6   14    70
C3               3   7     35
C4                   4     20
C5                         5

```