LC72 - 编辑距离

package DP2

func minDistance(word1 string, word2 string) int {
    size1, size2 := len(word1), len(word2)
    dp := make([][]int, size1+1)
    for i := 0; i <= size1; i++ {
        dp[i] = make([]int, size2+1)
    }
    // dp[i][j]: word1[0...i-1]变换到word2[0...j-1]的最小代价
    for j := 0; j <= size2; j++ {
        dp[0][j] = j
    }
    for i := 0; i <= size1; i++ {
        dp[i][0] = i
    }
    for i := 1; i <= size1; i++ {
        for j := 1; j <= size2; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
                // p1 = dp[i-1][j-1] + 1 -> 替换
                // p2 = dp[i][j-1] + 1   -> 插入
                // p3 = dp[i-1][j] + 1   -> 删除
            }
        }
    }
    return dp[size1][size2]
}

本题与上题 LC1143 非常相似，注释已经写得比较清楚。