72. Edit Distance 26 feb

class Solution {
public:
    int fun(int i,int j,string& word1,string& word2,vector<vector<int>> &dp)
    {
        if(j<0){
            return i+1;
        }
        if(i<0){
            return j+1;
        }
        if(dp[i][j]!=-1) return dp[i][j];
        if(word1[i]==word2[j]){
            return dp[i][j]=fun(i-1,j-1,word1,word2,dp);
        }
        int ins=1+fun(i,j-1,word1,word2,dp);
        int del=1+fun(i-1,j,word1,word2,dp);
        int rep=1+fun(i-1,j-1,word1,word2,dp);
        return dp[i][j]=min(ins,min(del,rep));
    }
    int minDistance(string word1, string word2) {
        int m=word1.size();
        int n=word2.size();
        vector<vector<int>> dp(m,vector<int>(n,-1));
        return fun(m-1,n-1,word1,word2,dp);
    }
};