public class MatrixMultOptMemoization {
    
    private static int[][] lookup;
    
    public static int f(int[][] mm) {
        lookup = new int[mm.length][mm.length];
        for (int[] l : lookup) {
            for (int i = 0; i < mm.length; i++) {
                l[i] = -1;
            }
        }
        return f(mm, 0, mm.length - 1);
    }

    public static int f(int[][] mm, int i, int j) {
        if (i >= j) // -> i == j ist unser Anker
            return 0;
        
        if (lookup[i][j] >= 0) // -> bereits enthalten
            return lookup[i][j];
        
        
        int min = Integer.MAX_VALUE; // Annahme: Minimum ist größter Integer
        
        for (int x = i; x < j; x++) {
            if (mm[x][1] != mm[x+1][0])
                throw new IllegalArgumentException(); 
            
            int amountOp = f(mm, i, x)
                         + f(mm, x+1, j)
                         + mm[i][0] * mm[x][1] * mm[j][1];
            
            if (amountOp < min)
                min = amountOp;
        }
        
        lookup[i][j] = min;
        return min;
    }
}