Matrix Chain Multiplication

Matrix Chain Multiplication 通常是在計算機科學和數學中討論的，其目標是找到一個最佳的矩陣相乘順序，以最小化計算矩陣相乘所需的總數量。

這種方法通常用於優化計算矩陣相乘的代價，例如減少計算時間或乘法運算的次數。

在矩陣鏈乘法中，我們有一個矩陣的序列，每個矩陣都有其自己的維度。

我們的目標是找到一個最佳的括號方式，以便在計算它們的乘積時最小化乘法操作的總數。

這需要動態規劃技術，通常使用一個矩陣來存儲子問題的最優解，以便在計算過程中重複使用。

矩陣鏈乘法是在優化計算機圖形和數據分析中非常有用的技術，它可以幫助我們更有效地處理大型數據集的數學運算，提高計算效率。

// Matrix Chain Multiplication in Kotlin
class MatrixChainMultiplication {
    fun matrixChainOrder(p: IntArray, n: Int): Int {
        val m = Array(n) { IntArray(n) }
        var i: Int
        var j: Int
        var k: Int
        var L: Int
        var q: Int
        i = 1
        while (i < n) {
            m[i][i] = 0
            i++
        }
        L = 2
        while (L < n) {
            i = 1
            while (i < n - L + 1) {
                j = i + L - 1
                if (j == n) {
                    continue
                }
                m[i][j] = Integer.MAX_VALUE
                k = i
                while (k <= j - 1) {
                    q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
                    if (q < m[i][j]) {
                        m[i][j] = q
                    }
                    k++
                }
                i++
            }
            L++
        }
        return m[1][n - 1]
    }
}

// main function
fun main(args: Array<String>) {
    val arr = intArrayOf(1, 2, 3, 4)
    val size = arr.size
    val mcm = MatrixChainMultiplication()
    println("Minimum number of multiplications is ${mcm.matrixChainOrder(arr, size)}")
}

Edit Distance

Edit Distance 是一種用來衡量兩個字串之間相似度的數學指標。

它衡量的是在將一個字串轉變為另一個字串時所需的最少編輯操作次數，這些編輯操作包括插入、刪除和替換字符。

編輯距離通常用於文字比對、拼寫檢查、自然語言處理和其他文本相似性分析的應用中。

藉由計算編輯距離，我們可以評估兩個字串之間的相似程度，並確定它們之間的差異有多大。

這在自動糾正拼寫錯誤、搜索引擎結果排序、字串匹配和文本相似性分析等領域中非常有用。

// Edit Distance Problem in Kotlin
class EditDistance {
    fun editDistDP(str1: String, str2: String, m: Int, n: Int): Int {
        val dp = Array(m + 1) { IntArray(n + 1) }
        for (i in 0..m) {
            for (j in 0..n) {
                if (i == 0) {
                    dp[i][j] = j
                } else if (j == 0) {
                    dp[i][j] = i
                } else if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1]
                } else {
                    dp[i][j] = 1 + Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1])
                }
            }
        }
        return dp[m][n]
    }
}

// main function
fun main(args: Array<String>) {
    val str1 = "sunday"
    val str2 = "saturday"
    val ed = EditDistance()
    println(ed.editDistDP(str1, str2, str1.length, str2.length))
}

所有 Code 可以在 Github 找到 ～

感謝大家，明天見！！！