72. 编辑距离

class Solution {
public:
    int minDistance(string s, string t) {
        // s[0:i-1] vs t[0:j-1] 最近编辑距离为dp[i][j]
        vector<vector<int>>dp(s.size()+1,vector<int>(t.size()+1,0));
        for(int j=1;j<t.size()+1;j++)dp[0][j]=j;
        for(int j=1;j<s.size()+1;j++)dp[j][0]=j;

        for(int i=1;i<s.size()+1;i++)
        for(int j=1;j<t.size()+1;j++)
        {
            if(s[i-1]==t[j-1]){
                dp[i][j]=dp[i-1][j-1];
            } else {
                dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
            }
        }
        return dp[s.size()][t.size()];
    }
};