66. 72. Edit Distance TOP-DOWN- I

class Solution {
    int dp[][] = new int[501][501];
    int m,n;
    public int minDistance(String word1, String word2) {
        m=word1.length();
        n=word2.length();
        for(int row[]:dp){
            Arrays.fill(row,-1);
        }
        return solve(word1,word2,0,0);
        
    }

    private int solve(String word1,String word2,int i,int j){
        if(i==m){
            return n-j;
        }else if(j==n){
            return m-i;
        }

        if(dp[i][j]!=-1){
            return dp[i][j];
        }

        if(word1.charAt(i)==word2.charAt(j)){
            return dp[i][j]=solve(word1,word2,i+1,j+1);
        }
        int insert =1+ solve(word1,word2,i,j+1);
        int delete =1+ solve(word1,word2,i+1,j);
        int replace =1+ solve(word1,word2,i+1,j+1);
        return dp[i][j]= Math.min(insert,Math.min(delete,replace));
    }
}