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
}