算法训练营day56_动态规划（3.18提前写）

583.两个字符串的删除操作

给定两个字符串，每次删除一个字符，使两个字符串相等的最小步数；

f(i,j)表示使s的前i个，t的前j个相等的最小步数；

转移；s[i] 与t[j]要么相等要么不相等；若相等，则从f(i-1,j-1)转移过来；若不等，要么删s[i]，要么删t[j]，从两个地方转移过来，看哪个步数少；

初始化；求最小，全初始为大值，f[0] [0]为0，并且s的前i个到t的前0个是i步，t的前i个到s的前0个是0步；

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1=word1.size(),n2=word2.size();
        vector<vector<int>> f(n1+1,vector<int>(n2+1,1001));
        for(int i=1;i<=n2;i++) f[0][i]=i;
        for(int i=1;i<=n1;i++) f[i][0]=i;
        f[0][0]=0;

        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                f[i][j]=min(f[i-1][j],f[i][j-1])+1;
                if(word1[i-1]==word2[j-1]) f[i][j]=f[i-1][j-1];
            }
        }
        return f[n1][n2];
    }
};

72.编辑距离

给定两个字符串s,t，使s变成t的最小步数（本题相对于上题，只能s->t，s除了删除，还可以插入，替换）；

草稿纸上列出来情况就很清晰的得出转移方程！s插入就相当于t删除，所以相比于上题，就多了个替换，替换就是f(i-1,j-1)+1;

• f(i,j)表示使s的前i个，t的前j个相等的最小步数；

• 转移；s[i] 与t[j]要么相等要么不相等；

  ​ 若相等，则从f(i-1,j-1)转移过来；

  ​ 若不等，要么删除，要么增加，要么替换，从三个地方转移过来，看哪个步数少；

• 初始化；求最小，全初始为大值，并且s的前i个到t的前0个是i步，t的前i个到s的前0个是0步；

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1=word1.size(),n2=word2.size();
        vector<vector<int>> f(n1+1,vector<int>(n2+1,1001));
        for(int i=0;i<=n2;i++) f[0][i]=i;
        for(int i=0;i<=n1;i++) f[i][0]=i;

        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                f[i][j]=min({f[i][j-1],f[i-1][j],f[i-1][j-1]})+1;
                if(word1[i-1]==word2[j-1]) f[i][j]=f[i-1][j-1];
            }
        }
        return f[n1][n2];
    }
};