We state the matrix-chain multiplication problem as follows: given a chain (A1,A2,…,An) of n matrices, where for i = 1,2,…,n, matrix Ai has dimension p[i-1]x p[i] , fully parenthesize the product A1A2...An in a way that minimizes the number of scalar multiplications.

longest common subsequence

fun matrixChainMultiplication(dimensions: IntArray): Int {
    val n = dimensions.size - 1
    val dp = Array(n) { IntArray(n) { 0 } }
    for (l in 1 until n) {
        for (i in 0 until n - l) {
            var min = Int.MAX_VALUE
            val j = i + l
            for (k in i until j) {
                val q = dp[i][k] + dp[k + 1][j] + dimensions[i] * dimensions[k + 1] * dimensions[j + 1]
                min = minOf(min, q)
            }
            dp[i][j] = min
        }
    }
    return dp.first().last()
}

There is memoized form of it too

longest common subsequence

fun matrixChainMultiplicationMemoized(dimensions: IntArray): Int {
    val dp = Array(dimensions.size - 1) { IntArray(dimensions.size - 1) { Int.MAX_VALUE } }
    return memoizedMultiplication(dimensions, 0, dimensions.lastIndex - 1, dp)
}

private fun memoizedMultiplication(dimensions: IntArray, start: Int, lastIndex: Int, dp: Array<IntArray>): Int {
    if (dp[start][lastIndex] != Int.MAX_VALUE) {
        return dp[start][lastIndex]
    }
    if (start == lastIndex) {
        dp[start][lastIndex] = 0
    } else {
        var result = Int.MAX_VALUE
        for (k in start until lastIndex) {
            val q = memoizedMultiplication(dimensions, start, k, dp) +
                    memoizedMultiplication(dimensions, k + 1, lastIndex, dp) +
                    dimensions[start] * dimensions[k + 1] * dimensions[lastIndex + 1]
            result = minOf(result, q)
        }
        dp[start][lastIndex] = result
    }
    return dp[start][lastIndex]
}