// https://de.wikipedia.org/wiki/Matrix-Kettenmultiplikation
// https://en.wikipedia.org/wiki/Matrix_chain_multiplication
public class MatrixMultOptimization {
    
    public static int f(int[][] mm) {
        return f(mm, 0, mm.length - 1);
    }

    public static int f(int[][] mm, int i, int j) {
        // 1. Teil der Formel:
        // wenn i = j, dann: f(i,j) = 0
        if (i >= j) // -> i == j ist unser Anker
            return 0;
        
        
        // 2. Teil der Formel:
        // 
        // sonst (wenn i < j, dann):
        // f(i,j) = min{f(i,x) + f(x+1,j) + (d1(i)*d2(x)*d2(j))
        //          wobei i <= x < j
        
        int min = Integer.MAX_VALUE; // Annahme: Minimum ist größter Integer
        
        /*
         * x:    0 steht für das Matrizenpaar an den Indizes 0 und 1
         *       1 steht für Paar mit den Indizes 1 und 2
         *       ...
         *       n-2 steht für n-2 und n-1 (die letzten beiden)
         * Allerdings gehen wir nicht von 0 bis mm.length-2 sondern
         * von i bis j-1, da die Funktion ja rekursiv ist und sich
         * der Bereich für mögliche Paare entsprechend verändert.
         * Außerdem bekommen wir für j den tatsächlich letzten Index,
         * weshalb j-1 das vorletzte Element ist.
         */
        for (int x = i; x < j; x++) {
            /* 
             * Fehlerbehandlung: Zwei aufeinanderfolgende Matrizen
             * müssen multiplizierbar sein. Falls das nicht so sein
             * sollte, werfen wir eine Exception. Das ist nicht
             * unbedingt nötig, da keine Fehlerbehanldung verlangt
             * war. Alternativ kann man auch eine Fehlermeldung per
             * System.out.println() ausgeben.
             */
            if (mm[x][1] != mm[x+1][0])
                throw new IllegalArgumentException(); 
            
            // d1 entspricht
            // Formel:
            int amountOp = f(mm, i, x)
                         + f(mm, x+1, j)
                         + mm[i][0] * mm[x][1] * mm[j][1];
            
            // Wir überprüfen ja mehrere x und wollen insgesamt das 
            // Minimum haben (der Menge aller möglichen Auswertungen):
            if (amountOp < min)
                min = amountOp;
        }
        
        return min;
    }
}