题解 | #编辑距离(一)#动态规划（状态方程）

class Solution {
public:
    /**
     dp[i][j]以i，j结尾的最少操作数
     dp[i][j]可以通过dp[i-1][j],dp[i][j-1], dp[i-1][j-1] 三种状态得到
     
     */
    int editDistance(string str1, string str2) {
        // write code here
        int len1 = str1.size();
        int len2 = str2.size();
        vector<vector<int> > dp(len1+1, vector<int>(len2+1, 0));
        for(int i=0;i<=len1; i++){
            dp[i][0]=i;
        }
        for(int j=0;j<=len2; j++){
            dp[0][j]=j;
        }
        for(int i=1;i<=len1; i++){
            for(int j=1; j<=len2;j++){
                int a = (str1[i-1]==str2[j-1])?0:1;
                dp[i][j] = min(1+dp[i-1][j], min(1+dp[i][j-1], a+dp[i-1][j-1]));
            }
        }
        return dp[len1][len2];
    }
};