kotlin coding test course, finding the minimum number of matrix multiplication operations

Matrix-related problems frequently appear in coding tests, and among them, matrix multiplication problems are a topic many candidates struggle with. In this article, we will examine the problem of ‘Finding the Minimum Number of Matrix Multiplication Operations’ and explain the algorithm and code to solve it in detail.

Problem Description

When the size of matrix A is A_rows x A_cols and the size of matrix B is B_rows x B_cols, to perform the multiplication of the two matrices, the number of columns in A A_cols must match the number of rows in B B_rows. The complexity of this operation is calculated as A_rows x A_cols x B_cols.

When multiplying multiple matrices, it is important to suitably select the ‘order of matrix multiplication’ to enhance operational efficiency. For a given list of matrices, we need to compute the number of operations for all possible multiplication orders and find the minimum.

Input Format

The first line contains a natural number N (1 ≤ N ≤ 30). The next N lines provide two integers R and C representing the size of each matrix. Here, R refers to the number of rows and C refers to the number of columns. It is assumed that the multiplication of each matrix is given in the form R×C.

Output Format

Print the minimum number of matrix multiplication operations on one line.

Example Input

Example Output

Solution Process

The algorithm used to solve this problem is the ‘Dynamic Programming Method for Deciding the Order of Matrix Multiplication’. By using this method, we can efficiently compute the multiplication operation cost for each matrix combination.

Dynamic Programming Approach

To determine the order of matrix multiplication for the given problem, we proceed with the following steps:

Create a DP table based on the entered matrix sizes.
Recursively calculate the multiplication ratio and update to the minimum value.
Finally, print the final value from the DP table.

DP Array and Initialization

First, we declare a two-dimensional array dp and initialize all values to 0. This array will store the minimum multiplication cost from matrix i to j in dp[i][j].

Operation Count Calculation Logic

To calculate the number of multiplication operations for the matrix, we proceed with the DP as follows:

Iterate through all possible intervals from i to j.
Select a midpoint k for the current interval (i ≤ k < j).
Calculate the costs of the two parts based on the current DP value and the midpoint, and sum them up.
Update the minimum value.

Code Implementation

Below is the code implemented in Kotlin for the above process:

    fun matrixChainOrder(dims: IntArray): Int {
        val n = dims.size - 1
        val dp = Array(n) { IntArray(n) }

        for (chainLength in 2..n) {
            for (i in 0..n - chainLength) {
                val j = i + chainLength - 1
                dp[i][j] = Int.MAX_VALUE
                for (k in i until j) {
                    val cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                    dp[i][j] = minOf(dp[i][j], cost)
                }
            }
        }
        return dp[0][n - 1]
    }

    fun main() {
        val n = readLine()!!.toInt()
        val dims = IntArray(n + 1)
        for (i in 0 until n) {
            val (r, c) = readLine()!!.split(" ").map { it.toInt() }
            dims[i] = r
            if (i == n - 1) {
                dims[i + 1] = c
            } else {
                dims[i + 1] = c
            }
        }
        println(matrixChainOrder(dims))
    }

Conclusion

Through this problem, we learned the optimization process of matrix multiplication, namely how to determine the optimal multiplication order. It is important to calculat the trivial parts step by step using dynamic programming to reduce the overall number of operations. Prepare adequately for these types of problems in coding tests, and practice repeatedly to gain an advantage. Next time, we will tackle even more in-depth problems!