C++ Coding Test Course, Finding the Minimum Number of Multiplications for Matrix Multiplication

Problem Description

There is a problem of finding the minimum number of operations required to multiply a given set of matrices.
If matrix A has a size of pq and matrix B has a size of qr, the number of operations required to multiply these two matrices is p * q * r.
We need to determine the order of matrix multiplication to minimize the total number of multiplication operations.

Problem Definition

Given n matrices with sizes as follows, find the minimum number of multiplication operations needed to multiply these matrices.

Input

The first line contains the number of matrices n (1 ≤ n ≤ 100).
The next n lines contain the size p_i × q_i of each matrix.

Output

Print the minimum number of operations required to multiply the matrices.

Example

Input:

Output:

Solution Process

1. Understanding the Basic Concept

Matrix multiplication is determined by the dimensions of the two matrices. Multiplying matrix A (p×q) and matrix B (q×r) results in matrix C (p×r).
The number of operations needed is p * q * r. If multiple matrices are provided, it is important to find the optimal multiplication order.

2. Utilizing Dynamic Programming

This problem can be solved using dynamic programming. We can construct a DP table to determine the optimal order of matrix multiplication.
Let dp[i][j] represent the minimum number of operations required to multiply from the ith matrix to the jth matrix.

3. Filling the DP Table

1. dp[i][i] = 0 (No operations are needed when multiplying a matrix with itself.)
2. When multiplying two or more matrices, divide the calculation based on the intermediate matrix.
3. The order of matrix multiplication is determined as follows.

for length from 2 to n:
    for i from 1 to n-length+1:
        j = i + length - 1
        dp[i][j] = ∞
        for k from i to j-1:
            cost = dp[i][k] + dp[k+1][j] + dimensions[i-1]*dimensions[k]*dimensions[j]
            dp[i][j] = min(dp[i][j], cost)

4. Python Implementation and C++ Code

Let’s implement the above algorithm in C++.

#include 
#include 
#include 

using namespace std;

int main() {
    int n;
    cin >> n;
    vector dimensions(n + 1);
    for (int i = 0; i < n; i++) {
        int p, q;
        cin >> p >> q;
        dimensions[i] = p;
        if (i == n - 1) dimensions[i + 1] = q; // last matrix's number of columns
    }

    vector> dp(n, vector(n, 0));

    for (int length = 2; length <= n; length++) {
        for (int i = 0; i < n - length + 1; 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];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }

    cout << dp[0][n - 1] << endl;
    return 0;
}

5. Time Complexity

The time complexity of this algorithm is O(n^3). This occurs because we need to consider all possible multiplication orders when there are n matrices.

6. Conclusion

The problem of minimizing matrix multiplication operations can be efficiently solved using dynamic programming.
This problem is very useful in developing algorithm problem-solving skills and is an important topic applicable in various fields.
By implementing this problem in C++, you can gain a deeper understanding of the concepts of algorithms and enhance your abilities to apply them in actual coding tests.