ClearAll[optim, aux]
optim[a_List] := Module[{u, v, n, c, r, s},
  n = Length[a] - 1;
  u = ConstantArray[0, {n, n}];
  v = ConstantArray[\[Infinity], {n, n}];
  u[[All, 1]] = -1;
  v[[All, 1]] = 0;
  Do[
   Do[
    Do[
     c =
      v[[i, k]] + v[[i + k, j - k]] + a[[i]] a[[i + k]] a[[i + j]];
      If[c < v[[i, j]],
       u[[i, j]] = k;
       v[[i, j]] = c;
      ]
     ,
     {k, 1, j - 1}
     ]
    ,
    {i, 1, n - j + 1}
    ]
   ,
   {j, 2, n}
   ];
  r = v[[1, n]];
  s = aux[u, 1, n];
  {r, s}
  ]
aux[u_, i_, j_] := Module[{k},
  k = u[[i, j]];
  If[k < 0,
   i
   ,
   Inactive[Times][aux[u, i, k], aux[u, i + k, j - k]]
   ]
  ]
{r, s} = optim[{1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2}];
r
s
{r, s} = optim[{1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10}];
r
s