Dim Shared As Integer U(), V()

Sub Aux(i As Integer, j As Integer)
    Dim As Integer k = U(i, j)
    If k < 0 Then
        Print Str(i);
    Else
        Print "(";
        Aux(i, k)
        Print "*";
        Aux(i + k, j - k)
        Print ")";
    End If
End Sub

Sub Optimize(a() As Integer)
    Dim As Integer i, j, k, c
    Dim As Integer n = Ubound(a) - 1
    Redim U(n, n), V(n, n)
    For i = 1 To n
        U(i, 1) = -1
        V(i, 1) = 0
    Next i

    For j = 2 To n
        For i = 1 To n - j + 1
            V(i, j) = &H7FFFFFFF
            For k = 1 To j - 1
                c = V(i, k) + V(i + k, j - k) + a(i) * a(i + k) * a(i + j)
                If c < V(i, j) Then
                    U(i, j) = k
                    V(i, j) = c
                End If
            Next k
        Next i
    Next j

    Print V(1, n); " ";
    Aux(1, n)
    Print
    Erase U, V
End Sub

Dim As Integer A1(1 To 4) = {5, 6, 3, 1}
Optimize(A1())
Dim As Integer A2(1 To 13) = {1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2}
Optimize(A2())
Dim As Integer A3(1 To 12) = {1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10}
Optimize(A3())

Sleep