AntInLoop

Matrix Chain Multiplication (Interval DP) Code Implementations

Complete Matrix Chain Multiplication (Interval DP) code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Matrix Chain Multiplication (Interval DP) Guide · Launch Interactive Visualizer

C++ Implementation

// Matrix Chain Multiplication Implementation in C++
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <climits>

class MatrixChainMultiplication {
public:
    static int matrixChainMultiplication(const std::vector<int>& dimensions) {
        int n = dimensions.size() - 1;
        std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
        std::vector<std::vector<int>> parenthesis(n, std::vector<int>(n, 0));
        
        // Fill the DP table diagonally
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp[i][j] = INT_MAX;
                
                for (int k = i; k < j; k++) {
                    int cost = dp[i][k] + dp[k + 1][j] + 
                              dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
                    
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                        parenthesis[i][j] = k;
                    }
                }
            }
        }
        
        return dp[0][n - 1];
    }
    
    // Matrix Chain Multiplication with parenthesis reconstruction
    struct MatrixChainResult {
        int minMultiplications;
        std::vector<std::vector<int>> parenthesis;
        std::string optimalParenthesis;
        
        MatrixChainResult(int minMult, const std::vector<std::vector<int>>& paren, 
                         const std::string& optParen) 
            : minMultiplications(minMult), parenthesis(paren), optimalParenthesis(optParen) {}
    };
    
    static MatrixChainResult matrixChainMultiplicationWithParenthesis(const std::vector<int>& dimensions) {
        int n = dimensions.size() - 1;
        std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
        std::vector<std::vector<int>> parenthesis(n, std::vector<int>(n, 0));
        
        // Fill the DP table diagonally
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp[i][j] = INT_MAX;
                
                for (int k = i; k < j; k++) {
                    int cost = dp[i][k] + dp[k + 1][j] + 
                              dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
                    
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                        parenthesis[i][j] = k;
                    }
                }
            }
        }
        
        std::string optimalParenthesis = buildParenthesis(parenthesis, 0, n - 1);
        
        return MatrixChainResult(dp[0][n - 1], parenthesis, optimalParenthesis);
    }
    
private:
    static std::string buildParenthesis(const std::vector<std::vector<int>>& parenthesis, int i, int j) {
        if (i == j) {
            return "A" + std::to_string(i + 1);
        }
        
        int k = parenthesis[i][j];
        std::string left = buildParenthesis(parenthesis, i, k);
        std::string right = buildParenthesis(parenthesis, k + 1, j);
        
        return "(" + left + " × " + right + ")";
    }
    
public:
    // Matrix Chain Multiplication with memoization (top-down approach)
    static int matrixChainMultiplicationMemo(const std::vector<int>& dimensions) {
        int n = dimensions.size() - 1;
        std::unordered_map<std::string, int> memo;
        
        return solveMemo(dimensions, 0, n - 1, memo);
    }
    
private:
    static int solveMemo(const std::vector<int>& dimensions, int i, int j, 
                        std::unordered_map<std::string, int>& memo) {
        if (i == j) return 0;
        
        std::string key = std::to_string(i) + "," + std::to_string(j);
        if (memo.find(key) != memo.end()) return memo[key];
        
        int minCost = INT_MAX;
        
        for (int k = i; k < j; k++) {
            int cost = solveMemo(dimensions, i, k, memo) + 
                      solveMemo(dimensions, k + 1, j, memo) + 
                      dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
            minCost = std::min(minCost, cost);
        }
        
        memo[key] = minCost;
        return minCost;
    }
    
public:
    // Matrix Chain Multiplication with detailed cost analysis
    struct CostBreakdown {
        int splitPoint;
        int leftCost;
        int rightCost;
        int currentCost;
        int totalCost;
        
        CostBreakdown(int split, int left, int right, int current, int total)
            : splitPoint(split), leftCost(left), rightCost(right), 
              currentCost(current), totalCost(total) {}
    };
    
    struct DetailedResult {
        int minMultiplications;
        std::vector<std::vector<int>> parenthesis;
        std::unordered_map<std::string, CostBreakdown> costBreakdown;
        
        DetailedResult(int minMult, const std::vector<std::vector<int>>& paren,
                      const std::unordered_map<std::string, CostBreakdown>& breakdown)
            : minMultiplications(minMult), parenthesis(paren), costBreakdown(breakdown) {}
    };
    
    static DetailedResult matrixChainMultiplicationDetailed(const std::vector<int>& dimensions) {
        int n = dimensions.size() - 1;
        std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
        std::vector<std::vector<int>> parenthesis(n, std::vector<int>(n, 0));
        std::unordered_map<std::string, CostBreakdown> costBreakdown;
        
        // Fill the DP table diagonally
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp[i][j] = INT_MAX;
                
                for (int k = i; k < j; k++) {
                    int leftCost = dp[i][k];
                    int rightCost = dp[k + 1][j];
                    int currentCost = dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
                    int totalCost = leftCost + rightCost + currentCost;
                    
                    if (totalCost < dp[i][j]) {
                        dp[i][j] = totalCost;
                        parenthesis[i][j] = k;
                        
                        std::string key = std::to_string(i) + "," + std::to_string(j);
                        costBreakdown[key] = CostBreakdown(k, leftCost, rightCost, currentCost, totalCost);
                    }
                }
            }
        }
        
        return DetailedResult(dp[0][n - 1], parenthesis, costBreakdown);
    }
    
    // Matrix Chain Multiplication with validation
    static int matrixChainMultiplicationWithValidation(const std::vector<int>& dimensions) {
        // Validate input
        if (dimensions.size() < 2) {
            throw std::invalid_argument("At least 2 dimensions are required");
        }
        
        for (size_t i = 0; i < dimensions.size() - 1; i++) {
            if (dimensions[i] <= 0 || dimensions[i + 1] <= 0) {
                throw std::invalid_argument("All dimensions must be positive");
            }
        }
        
        // Check if matrices can be multiplied
        for (size_t i = 0; i < dimensions.size() - 2; i++) {
            if (dimensions[i + 1] != dimensions[i + 2]) {
                throw std::invalid_argument("Matrices cannot be multiplied in the given order");
            }
        }
        
        return matrixChainMultiplication(dimensions);
    }
    
    // Helper function to calculate cost of multiplying two matrices
    static int matrixMultiplyCost(int rows1, int cols1, int cols2) {
        return rows1 * cols1 * cols2;
    }
    
    // Helper function to get matrix dimensions from a sequence
    static std::vector<int> getMatrixDimensions(const std::vector<std::vector<std::vector<int>>>& matrices) {
        std::vector<int> dimensions(matrices.size() + 1);
        for (size_t i = 0; i < matrices.size(); i++) {
            if (i == 0) {
                dimensions[i] = matrices[i].size(); // rows of first matrix
            }
            dimensions[i + 1] = matrices[i][0].size(); // cols of current matrix
        }
        return dimensions;
    }
};

JAVA Implementation

// Matrix Chain Multiplication Implementation in Java
public class MatrixChainMultiplication {
    public static int matrixChainMultiplication(int[] dimensions) {
        int n = dimensions.length - 1;
        int[][] dp = new int[n][n];
        int[][] parenthesis = new int[n][n];
        
        // Fill the DP table diagonally
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp[i][j] = Integer.MAX_VALUE;
                
                for (int k = i; k < j; k++) {
                    int cost = dp[i][k] + dp[k + 1][j] + 
                              dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
                    
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                        parenthesis[i][j] = k;
                    }
                }
            }
        }
        
        return dp[0][n - 1];
    }
    
    // Matrix Chain Multiplication with parenthesis reconstruction
    public static class MatrixChainResult {
        public int minMultiplications;
        public int[][] parenthesis;
        public String optimalParenthesis;
        
        public MatrixChainResult(int minMultiplications, int[][] parenthesis, String optimalParenthesis) {
            this.minMultiplications = minMultiplications;
            this.parenthesis = parenthesis;
            this.optimalParenthesis = optimalParenthesis;
        }
    }
    
    public static MatrixChainResult matrixChainMultiplicationWithParenthesis(int[] dimensions) {
        int n = dimensions.length - 1;
        int[][] dp = new int[n][n];
        int[][] parenthesis = new int[n][n];
        
        // Fill the DP table diagonally
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp[i][j] = Integer.MAX_VALUE;
                
                for (int k = i; k < j; k++) {
                    int cost = dp[i][k] + dp[k + 1][j] + 
                              dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
                    
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                        parenthesis[i][j] = k;
                    }
                }
            }
        }
        
        String optimalParenthesis = buildParenthesis(parenthesis, 0, n - 1);
        
        return new MatrixChainResult(dp[0][n - 1], parenthesis, optimalParenthesis);
    }
    
    private static String buildParenthesis(int[][] parenthesis, int i, int j) {
        if (i == j) {
            return "A" + (i + 1);
        }
        
        int k = parenthesis[i][j];
        String left = buildParenthesis(parenthesis, i, k);
        String right = buildParenthesis(parenthesis, k + 1, j);
        
        return "(" + left + " × " + right + ")";
    }
    
    // Matrix Chain Multiplication with memoization (top-down approach)
    public static int matrixChainMultiplicationMemo(int[] dimensions) {
        int n = dimensions.length - 1;
        java.util.Map<String, Integer> memo = new java.util.HashMap<>();
        
        return solveMemo(dimensions, 0, n - 1, memo);
    }
    
    private static int solveMemo(int[] dimensions, int i, int j, java.util.Map<String, Integer> memo) {
        if (i == j) return 0;
        
        String key = i + "," + j;
        if (memo.containsKey(key)) return memo.get(key);
        
        int minCost = Integer.MAX_VALUE;
        
        for (int k = i; k < j; k++) {
            int cost = solveMemo(dimensions, i, k, memo) + 
                      solveMemo(dimensions, k + 1, j, memo) + 
                      dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
            minCost = Math.min(minCost, cost);
        }
        
        memo.put(key, minCost);
        return minCost;
    }
    
    // Matrix Chain Multiplication with detailed cost analysis
    public static class DetailedResult {
        public int minMultiplications;
        public int[][] parenthesis;
        public java.util.Map<String, Object> costBreakdown;
        
        public DetailedResult(int minMultiplications, int[][] parenthesis, 
                            java.util.Map<String, Object> costBreakdown) {
            this.minMultiplications = minMultiplications;
            this.parenthesis = parenthesis;
            this.costBreakdown = costBreakdown;
        }
    }
    
    public static DetailedResult matrixChainMultiplicationDetailed(int[] dimensions) {
        int n = dimensions.length - 1;
        int[][] dp = new int[n][n];
        int[][] parenthesis = new int[n][n];
        java.util.Map<String, Object> costBreakdown = new java.util.HashMap<>();
        
        // Fill the DP table diagonally
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp[i][j] = Integer.MAX_VALUE;
                
                for (int k = i; k < j; k++) {
                    int leftCost = dp[i][k];
                    int rightCost = dp[k + 1][j];
                    int currentCost = dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
                    int totalCost = leftCost + rightCost + currentCost;
                    
                    if (totalCost < dp[i][j]) {
                        dp[i][j] = totalCost;
                        parenthesis[i][j] = k;
                        
                        java.util.Map<String, Object> breakdown = new java.util.HashMap<>();
                        breakdown.put("splitPoint", k);
                        breakdown.put("leftCost", leftCost);
                        breakdown.put("rightCost", rightCost);
                        breakdown.put("currentCost", currentCost);
                        breakdown.put("totalCost", totalCost);
                        
                        costBreakdown.put(i + "," + j, breakdown);
                    }
                }
            }
        }
        
        return new DetailedResult(dp[0][n - 1], parenthesis, costBreakdown);
    }
    
    // Matrix Chain Multiplication with validation
    public static int matrixChainMultiplicationWithValidation(int[] dimensions) {
        // Validate input
        if (dimensions == null || dimensions.length < 2) {
            throw new IllegalArgumentException("At least 2 dimensions are required");
        }
        
        for (int i = 0; i < dimensions.length - 1; i++) {
            if (dimensions[i] <= 0 || dimensions[i + 1] <= 0) {
                throw new IllegalArgumentException("All dimensions must be positive");
            }
        }
        
        // Check if matrices can be multiplied
        for (int i = 0; i < dimensions.length - 2; i++) {
            if (dimensions[i + 1] != dimensions[i + 2]) {
                throw new IllegalArgumentException("Matrices cannot be multiplied in the given order");
            }
        }
        
        return matrixChainMultiplication(dimensions);
    }
    
    // Helper function to calculate cost of multiplying two matrices
    public static int matrixMultiplyCost(int rows1, int cols1, int cols2) {
        return rows1 * cols1 * cols2;
    }
    
    // Helper function to get matrix dimensions from a sequence
    public static int[] getMatrixDimensions(int[][][] matrices) {
        int[] dimensions = new int[matrices.length + 1];
        for (int i = 0; i < matrices.length; i++) {
            if (i == 0) {
                dimensions[i] = matrices[i].length; // rows of first matrix
            }
            dimensions[i + 1] = matrices[i][0].length; // cols of current matrix
        }
        return dimensions;
    }
}

JAVASCRIPT Implementation

// Matrix Chain Multiplication Implementation in JavaScript
function matrixChainMultiplication(dimensions) {
  const n = dimensions.length - 1;
  const dp = Array(n).fill().map(() => Array(n).fill(0));
  const parenthesis = Array(n).fill().map(() => Array(n).fill(0));
  
  // Fill the DP table diagonally
  for (let length = 2; length <= n; length++) {
    for (let i = 0; i <= n - length; i++) {
      const j = i + length - 1;
      dp[i][j] = Infinity;
      
      for (let k = i; k < j; k++) {
        const cost = dp[i][k] + dp[k + 1][j] + 
                    dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
        
        if (cost < dp[i][j]) {
          dp[i][j] = cost;
          parenthesis[i][j] = k;
        }
      }
    }
  }
  
  return {
    minMultiplications: dp[0][n - 1],
    parenthesis: parenthesis
  };
}

// Matrix Chain Multiplication with parenthesis reconstruction
function matrixChainMultiplicationWithParenthesis(dimensions) {
  const result = matrixChainMultiplication(dimensions);
  const parenthesis = result.parenthesis;
  
  function buildParenthesis(i, j) {
    if (i === j) {
      return 'A' + (i + 1);
    }
    
    const k = parenthesis[i][j];
    const left = buildParenthesis(i, k);
    const right = buildParenthesis(k + 1, j);
    
    return '(' + left + ' × ' + right + ')';
  }
  
  const optimalParenthesis = buildParenthesis(0, dimensions.length - 2);
  
  return {
    minMultiplications: result.minMultiplications,
    optimalParenthesis: optimalParenthesis
  };
}

// Matrix Chain Multiplication with memoization (top-down approach)
function matrixChainMultiplicationMemo(dimensions) {
  const n = dimensions.length - 1;
  const memo = new Map();
  
  function solve(i, j) {
    if (i === j) return 0;
    
    const key = i + ',' + j;
    if (memo.has(key)) return memo.get(key);
    
    let minCost = Infinity;
    
    for (let k = i; k < j; k++) {
      const cost = solve(i, k) + solve(k + 1, j) + 
                  dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
      minCost = Math.min(minCost, cost);
    }
    
    memo.set(key, minCost);
    return minCost;
  }
  
  return solve(0, n - 1);
}

// Matrix Chain Multiplication with detailed cost analysis
function matrixChainMultiplicationDetailed(dimensions) {
  const n = dimensions.length - 1;
  const dp = Array(n).fill().map(() => Array(n).fill(0));
  const parenthesis = Array(n).fill().map(() => Array(n).fill(0));
  const costBreakdown = Array(n).fill().map(() => Array(n).fill(null));
  
  // Fill the DP table diagonally
  for (let length = 2; length <= n; length++) {
    for (let i = 0; i <= n - length; i++) {
      const j = i + length - 1;
      dp[i][j] = Infinity;
      
      for (let k = i; k < j; k++) {
        const leftCost = dp[i][k];
        const rightCost = dp[k + 1][j];
        const currentCost = dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
        const totalCost = leftCost + rightCost + currentCost;
        
        if (totalCost < dp[i][j]) {
          dp[i][j] = totalCost;
          parenthesis[i][j] = k;
          costBreakdown[i][j] = {
            splitPoint: k,
            leftCost: leftCost,
            rightCost: rightCost,
            currentCost: currentCost,
            totalCost: totalCost
          };
        }
      }
    }
  }
  
  return {
    minMultiplications: dp[0][n - 1],
    parenthesis: parenthesis,
    costBreakdown: costBreakdown
  };
}

// Matrix Chain Multiplication with space optimization
function matrixChainMultiplicationOptimized(dimensions) {
  const n = dimensions.length - 1;
  const dp = Array(n).fill().map(() => Array(n).fill(0));
  
  // Fill the DP table diagonally
  for (let length = 2; length <= n; length++) {
    for (let i = 0; i <= n - length; i++) {
      const j = i + length - 1;
      dp[i][j] = Infinity;
      
      for (let k = i; k < j; k++) {
        const cost = dp[i][k] + dp[k + 1][j] + 
                    dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
        dp[i][j] = Math.min(dp[i][j], cost);
      }
    }
  }
  
  return dp[0][n - 1];
}

// Matrix Chain Multiplication with validation
function matrixChainMultiplicationWithValidation(dimensions) {
  // Validate input
  if (!dimensions || dimensions.length < 2) {
    throw new Error('At least 2 dimensions are required');
  }
  
  for (let i = 0; i < dimensions.length - 1; i++) {
    if (dimensions[i] <= 0 || dimensions[i + 1] <= 0) {
      throw new Error('All dimensions must be positive');
    }
  }
  
  // Check if matrices can be multiplied
  for (let i = 0; i < dimensions.length - 2; i++) {
    if (dimensions[i + 1] !== dimensions[i + 2]) {
      throw new Error('Matrices cannot be multiplied in the given order');
    }
  }
  
  return matrixChainMultiplication(dimensions);
}

// Helper function to calculate cost of multiplying two matrices
function matrixMultiplyCost(rows1, cols1, cols2) {
  return rows1 * cols1 * cols2;
}

// Helper function to get matrix dimensions from a sequence
function getMatrixDimensions(matrices) {
  const dimensions = [];
  for (let i = 0; i < matrices.length; i++) {
    if (i === 0) {
      dimensions.push(matrices[i].length); // rows of first matrix
    }
    dimensions.push(matrices[i][0].length); // cols of current matrix
  }
  return dimensions;
}

PYTHON Implementation

# Matrix Chain Multiplication Implementation in Python
def matrix_chain_multiplication(dimensions):
    n = len(dimensions) - 1
    dp = [[0] * n for _ in range(n)]
    parenthesis = [[0] * n for _ in range(n)]
    
    # Fill the DP table diagonally
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] +                        dimensions[i] * dimensions[k + 1] * dimensions[j + 1]
                
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    parenthesis[i][j] = k
    
    return {
        'min_multiplications': dp[0][n - 1],
        'parenthesis': parenthesis
    }

# Matrix Chain Multiplication with parenthesis reconstruction
def matrix_chain_multiplication_with_parenthesis(dimensions):
    result = matrix_chain_multiplication(dimensions)
    parenthesis = result['parenthesis']
    
    def build_parenthesis(i, j):
        if i == j:
            return f'A{i + 1}'
        
        k = parenthesis[i][j]
        left = build_parenthesis(i, k)
        right = build_parenthesis(k + 1, j)
        
        return f'({left} × {right})'
    
    optimal_parenthesis = build_parenthesis(0, len(dimensions) - 2)
    
    return {
        'min_multiplications': result['min_multiplications'],
        'optimal_parenthesis': optimal_parenthesis
    }

# Matrix Chain Multiplication with memoization (top-down approach)
def matrix_chain_multiplication_memo(dimensions):
    n = len(dimensions) - 1
    memo = {}
    
    def solve(i, j):
        if i == j:
            return 0
        
        if (i, j) in memo:
            return memo[(i, j)]
        
        min_cost = float('inf')
        
        for k in range(i, j):
            cost = solve(i, k) + solve(k + 1, j) +                    dimensions[i] * dimensions[k + 1] * dimensions[j + 1]
            min_cost = min(min_cost, cost)
        
        memo[(i, j)] = min_cost
        return min_cost
    
    return solve(0, n - 1)

# Matrix Chain Multiplication with detailed cost analysis
def matrix_chain_multiplication_detailed(dimensions):
    n = len(dimensions) - 1
    dp = [[0] * n for _ in range(n)]
    parenthesis = [[0] * n for _ in range(n)]
    cost_breakdown = [[None] * n for _ in range(n)]
    
    # Fill the DP table diagonally
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            
            for k in range(i, j):
                left_cost = dp[i][k]
                right_cost = dp[k + 1][j]
                current_cost = dimensions[i] * dimensions[k + 1] * dimensions[j + 1]
                total_cost = left_cost + right_cost + current_cost
                
                if total_cost < dp[i][j]:
                    dp[i][j] = total_cost
                    parenthesis[i][j] = k
                    cost_breakdown[i][j] = {
                        'split_point': k,
                        'left_cost': left_cost,
                        'right_cost': right_cost,
                        'current_cost': current_cost,
                        'total_cost': total_cost
                    }
    
    return {
        'min_multiplications': dp[0][n - 1],
        'parenthesis': parenthesis,
        'cost_breakdown': cost_breakdown
    }

# Matrix Chain Multiplication with space optimization
def matrix_chain_multiplication_optimized(dimensions):
    n = len(dimensions) - 1
    dp = [[0] * n for _ in range(n)]
    
    # Fill the DP table diagonally
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] +                        dimensions[i] * dimensions[k + 1] * dimensions[j + 1]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n - 1]

# Matrix Chain Multiplication with validation
def matrix_chain_multiplication_with_validation(dimensions):
    # Validate input
    if not dimensions or len(dimensions) < 2:
        raise ValueError('At least 2 dimensions are required')
    
    for i in range(len(dimensions) - 1):
        if dimensions[i] <= 0 or dimensions[i + 1] <= 0:
            raise ValueError('All dimensions must be positive')
    
    # Check if matrices can be multiplied
    for i in range(len(dimensions) - 2):
        if dimensions[i + 1] != dimensions[i + 2]:
            raise ValueError('Matrices cannot be multiplied in the given order')
    
    return matrix_chain_multiplication(dimensions)

# Helper function to calculate cost of multiplying two matrices
def matrix_multiply_cost(rows1, cols1, cols2):
    return rows1 * cols1 * cols2

# Helper function to get matrix dimensions from a sequence
def get_matrix_dimensions(matrices):
    dimensions = []
    for i, matrix in enumerate(matrices):
        if i == 0:
            dimensions.append(len(matrix))  # rows of first matrix
        dimensions.append(len(matrix[0]))   # cols of current matrix
    return dimensions

# Matrix Chain Multiplication with step-by-step execution
def matrix_chain_multiplication_steps(dimensions):
    n = len(dimensions) - 1
    dp = [[0] * n for _ in range(n)]
    parenthesis = [[0] * n for _ in range(n)]
    steps = []
    
    # Fill the DP table diagonally
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            
            step_info = {
                'length': length,
                'i': i,
                'j': j,
                'candidates': []
            }
            
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] +                        dimensions[i] * dimensions[k + 1] * dimensions[j + 1]
                
                candidate = {
                    'k': k,
                    'left_cost': dp[i][k],
                    'right_cost': dp[k + 1][j],
                    'current_cost': dimensions[i] * dimensions[k + 1] * dimensions[j + 1],
                    'total_cost': cost
                }
                step_info['candidates'].append(candidate)
                
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    parenthesis[i][j] = k
                    step_info['chosen_k'] = k
                    step_info['final_cost'] = cost
            
            steps.append(step_info)
    
    return {
        'min_multiplications': dp[0][n - 1],
        'parenthesis': parenthesis,
        'steps': steps
    }