簡單線性動態規劃 ―― 編輯距離

可用滾動數組壓縮空間，略

if s[i] = t[j] then
    dp[i, j] := dp[i-1, j-1]          // no operation required
else
    dp[i, j] := min(
                         dp[i-1, j] + 1,     // a deletion
                         dp[i, j-1] + 1,     // an insertion
                         dp[i-1, j-1] + 1  // a substitution
                     )

加權的情況：

dp[i][j] := min( dp[i - 1][j] + delCost, min( dp[i][j - 1] + delCost, dp[i - 1][j - 1] + changeCost ) )

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈