Matrix Chain Multiplication क्या है

Matrix chain multiplication tables के एक stack को multiply करने का सबसे अच्छा order decide करने जैसा है ताकि आप कम से कम total work करें।

In this page:

Problem Idea
Cost Formula
DP State
Optimal Split
Practice

Syntax

markup

for length in range(2, n):
    for i in range(1, 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] + p[i - 1] * p[k] * p[j]
            dp[i][j] = min(dp[i][j], cost)

Problem Idea

Matrices की एक chain को एक साथ multiply करते समय, चाहिए scalar multiplications की total संख्या काफी हद तक इस पर निर्भर करती है कि आप multiplications को कैसे group करते हैं — यह problem वह grouping (parenthesization) ढूंढती है जो उस total cost को minimize करे।

उदाहरण: Problem Idea

#include <iostream>
using namespace std;
int main() {
	int dims[] = {10, 20, 30, 40};
	cout << "3 matrices chained -- grouping order changes total scalar multiplications needed";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] dims = {10, 20, 30, 40};
		System.out.println("3 matrices chained -- grouping order changes total scalar multiplications needed");
	}
}

dims = [10, 20, 30, 40]
print("3 matrices chained -- grouping order changes total scalar multiplications needed")

#include <stdio.h>
int main() {
	int dims[] = {10, 20, 30, 40};
	printf("3 matrices chained -- grouping order changes total scalar multiplications needed");
	return 0;
}

Cost Formula

एक p×q matrix को एक q×r matrix से multiply करने में बिल्कुल p × q × r individual multiplications लगते हैं, इसलिए chain को split करने का हर possible तरीका एक computable cost रखता है, और goal वह split ढूंढना है जो सबसे छोटे total तक add हो।

उदाहरण: Cost Formula

#include <iostream>
using namespace std;
int main() {
	int p = 10, q = 20, r = 30;
	cout << "Multiplying " << p << "x" << q << " by " << q << "x" << r << " costs " << p*q*r << " multiplications";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int p = 10, q = 20, r = 30;
		System.out.println("Multiplying " + p + "x" + q + " by " + q + "x" + r + " costs " + (p*q*r) + " multiplications");
	}
}

p, q, r = 10, 20, 30
print(f"Multiplying {p}x{q} by {q}x{r} costs {p*q*r} multiplications")

#include <stdio.h>
int main() {
	int p = 10, q = 20, r = 30;
	printf("Multiplying %dx%d by %dx%d costs %d multiplications", p, q, q, r, p*q*r);
	return 0;
}

DP State

dp[i][j] index i से index j तक matrices के contiguous run को multiply करने की minimum cost store करता है, इसलिए छोटे ranges पहले solve होते हैं और बड़े ranges का answer देने के लिए combine होते हैं।

उदाहरण: DP State

#include <iostream>
using namespace std;
int main() {
	int dp[4][4] = {0};
	cout << "dp[i][j] = minimum cost to multiply matrices i through j; smaller ranges solved before larger";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[][] dp = new int[4][4];
		System.out.println("dp[i][j] = minimum cost to multiply matrices i through j; smaller ranges solved before larger");
	}
}

dp = [[0]*4 for _ in range(4)]
print("dp[i][j] = minimum cost to multiply matrices i through j; smaller ranges solved before larger")

#include <stdio.h>
int main() {
	int dp[4][4] = {0};
	printf("dp[i][j] = minimum cost to multiply matrices i through j; smaller ranges solved before larger");
	return 0;
}

Optimal Split

Matrices के एक दिए range के लिए, algorithm इसे एक left group और एक right group में split करने की हर possible point try करता है, हर split की cost compute करता है (left cost + right cost + दोनों resulting matrices को एक साथ multiply करने की cost), और सबसे सस्ती रखता है।

उदाहरण: Optimal Split

#include <iostream>
using namespace std;
int main() {
	int dims[] = {10,20,30,40};
	int n = 3;
	int dp[4][4] = {0};
	for (int len = 2; len <= n; len++)
		for (int i = 1; i <= n-len+1; i++) {
			int j = i+len-1;
			dp[i][j] = 1000000000;
			for (int k = i; k < j; k++) {
				int cost = dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j];
				dp[i][j] = min(dp[i][j], cost);
			}
		}
	cout << "Minimum total cost: " << dp[1][n];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] dims = {10,20,30,40};
		int n = 3;
		int[][] dp = new int[4][4];
		for (int len = 2; len <= n; len++)
			for (int i = 1; i <= n-len+1; i++) {
				int j = i+len-1;
				dp[i][j] = 1000000000;
				for (int k = i; k < j; k++) {
					int cost = dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j];
					dp[i][j] = Math.min(dp[i][j], cost);
				}
			}
		System.out.println("Minimum total cost: " + dp[1][n]);
	}
}

dims = [10,20,30,40]
n = 3
dp = [[0]*(n+1) for _ in range(n+1)]
for length in range(2, n+1):
    for i in range(1, n-length+2):
        j = i+length-1
        dp[i][j] = float('inf')
        for k in range(i, j):
            cost = dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j]
            dp[i][j] = min(dp[i][j], cost)
print("Minimum total cost:", dp[1][n])

#include <stdio.h>
int main() {
	int dims[] = {10,20,30,40};
	int n = 3;
	int dp[4][4] = {0};
	for (int len = 2; len <= n; len++)
		for (int i = 1; i <= n-len+1; i++) {
			int j = i+len-1;
			dp[i][j] = 1000000000;
			for (int k = i; k < j; k++) {
				int cost = dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j];
				if (cost < dp[i][j]) dp[i][j] = cost;
			}
		}
	printf("Minimum total cost: %d", dp[1][n]);
	return 0;
}

Practice

यह interval DP का एक textbook example है, जहां subproblems prefixes के बजाय contiguous ranges [i, j] पर defined हैं — वही pattern optimal polygon triangulation और burst-balloon-style puzzles जैसी problems में फिर दिखता है।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Interval DP over ranges [i,j] -- same pattern as optimal polygon triangulation";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Interval DP over ranges [i,j] -- same pattern as optimal polygon triangulation");
	}
}

print("Interval DP over ranges [i,j] -- same pattern as optimal polygon triangulation")

#include <stdio.h>
int main() {
	printf("Interval DP over ranges [i,j] -- same pattern as optimal polygon triangulation");
	return 0;
}

Chapter Quiz — Complete all 12 topics to unlock

0/12 topics done

Complete these topics first:

← Previous Lesson Coin Change Problem Next Lesson → DP on Grids