2つの単語word 1とword 2を与える、word 1をword 2に変換するために必要な最小ステップ数とする.次の3つの操作で1つの字を許可します:a)1つの文字bを挿入します)1つの文字cを削除します)1つの文字を置き換えます

本題はLeetCodeに由来する
----------------------------------------------------------------------
構想動的計画
変化が必要なステップ数をdp配列で記録します.dp[i]【j】は、文字列長がiから文字列長jになるために必要なステップ数を表す
コード:

    int minDistance(string word1, string word2) {
        int len1=word1.length();
        int len2=word2.length();
        
        vector>dp(len1+1,vector(len2+1));
        for(int i=0;i<=len1;i++){
            for(int j=0;j<=len2;j++){
                if(i==0){
                    dp[i][j]=j;   //   i=0      j   
                }else if(j==0){
                    dp[i][j]=i;    //  j=0     i   
                }else if(word1[i-1]==word2[j-1]){   //           ，           
                    dp[i][j]=dp[i-1][j-1];
                }else{                          //       ，  ，           1 
                    dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                }
            }
        }
        return dp[len1][len2];
    }