題目描述

給定兩個字符串A和B，現(xiàn)在要將A經(jīng)過若干操作變?yōu)锽，可進行的操作有：
刪除–將字符串A中的某個字符刪除。
插入–在字符串A的某個位置插入某個字符。
替換–將字符串A中的某個字符替換為另一個字符。
現(xiàn)在請你求出，將A變?yōu)锽至少需要進行多少次操作。

思路 動態(tài)規(guī)劃

• dp[i][j]
  • 集合 ： 所有吧a中的前i個字母 變成 b中前j個字母的集合的操作集合
  • 屬性 ： 所有操作中操作次數(shù)最少的方案的操作數(shù)
• 狀態(tài)計算
  以對a中的第i個字母操作不同劃分
  • 在該字母之后添加
    • 添加一個字母之后變得相同，說明沒有添加前a的前i個已經(jīng)和b的前j-1個已經(jīng)相同
    • 即 ： dp[i][j] = dp[i][j-1] + 1
  • 刪除該字母
    • 刪除該字母之后變得相同，說明沒有刪除前a中前i-1已經(jīng)和b的前j個已經(jīng)相同
    • 即 ： dp[i][j] = dp[i-1][j] + 1
  • 替換該字母
    • 替換說明對應結尾字母不同，則看倒數(shù)第二個
    • 即： dp[i][j] = dp[i-1][j-1] + 1
  • 啥也不做
    • 對應結尾字母相同，直接比較倒數(shù)第二個
    • 即： dp[i][j] = dp[i-1][j-1]

#include <iostream>
#include <string>
#include <vector>

using namespace std;


int leastEdit(string a, string b){
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1));
    
    for(int i = 0; i <= m; i++) dp[i][0] = i;
    for(int i = 0; i <= n; i++) dp[0][i] = i;
    
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + 1;  // 添加 和 刪除 
            dp[i][j] = min(dp[i][j], dp[i-1][j-1] + (a[i - 1] != b[j - 1])); // 替換和 啥也不做
        }
    }
    return dp[m][n];
}


int main(){
    int a, b;
    string s1, s2;
    
    cin >> a >> s1 >> b >> s2;
    cout << leastEdit(s1, s2);
    
    return 0;
    
}