matrix chain multiplication dynamic programming time complexity code example

Example: matrix chain multiplication

minimum_multiplication(n: integer; d: array(0..n))
        M: array(1..n, 1..n) := (others => 0);

        for diagonal in 1 .. n-1 loop 
            for i in 1 .. n - diagonal loop 
                j := i + diagonal;

                min := integer'last;
                for k in i .. j-1 loop
                    current := M[i, k] + M[k+1, j] + d(i-1)*d(k)*d(j) 
                    if current < min then
                        min := current
                    end if
                end loop
                M[i, j] := min
            end loop
        end loop

Tags:

Misc Example