Matrix Chain Multiplication (Bottom-Up)
Partition DP & MCM DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Tabulation approach for solving Matrix Chain Multiplication (MCM), Dynamic Programming, Memoization, Tabulation, Recursion, Time Complexity, Space Complexity, Big O Notation, Matrices, Overlapping Subproblems, Optimal Substructure, Base Cases, memoization, complexity analysis, tabulation, dynamic programming, Partition DP, 1D & 2D DP.
Matrix Chain Multiplication Problem Statement Given a sequence of matrices, find the most efficient way to multiply these matrices. The problem is to determine the minimum number of scalar multiplications needed to multiply the chain of matrices. More precisely, you are given an array P of size N, where P[i 1] and P[i] are the dimensions of the i th matrix. That is, matrix M i has dimensions P[i 1] x P[i]. You need to find the minimum number of scalar multiplications required to multiply the chain of matrices M 1 M 2 ... M {N 1}. For example, if the matrices are A(10x20), B(20x30), C(30x40), D(40x50), the input array P would be [10, 20, 30, 40, 50] with N=5. Input Specification The first line contains an integer N, representing the number of dimensions in the P array (which is number of matrices + 1). The second line contains N space separated integers P 0, P 1, ..., P {N 1}, representing the dimensions array P. Output Specification Return a single integer: the minimum number of scalar multiplications required. Constraints 2 <= N <= 100 1 <= P[i] <= 500 Sample Test Case Input Output Explanation The input [10, 20, 30, 40, 50] represents four matrices: A1: 10x20 A2: 20x30 A3: 30x40 A4: 40x50 The optimal parenthesization leads to 38000 scalar multiplications.