Very detailed explanation (Recursive -> DP ) in Java
The first step towards solving a DP problem is to build up the recursion tree. Once you have done it, it could be optimized using memoization, or a bottoms-up. 
The first step towards solving a DP problem is to build up the recursion tree. Once you have done it, it could be optimized using memoization, or a bottoms-up. Memoization is no brainer but bottoms-up takes a bit to get it right. I will try to outline how to build up the recursive solution and then move to DP from there. \n\nThis algorithm is based on standard L-distance, where would you do something of this sort:\n```\nif two characters are not equal:\n\t//cost to replace\n\tint replaceCount = 1 + function(s1, i+1, s2, j+1); // add 1 to the cost of replacing a character and go to the next set of characters.\n\t//cost to delete.\n\tint deleteCount = 1 + function(s1, i+1, s2, j); //add 1 to the cost of deleting the current char from string 1 and move to the next character from the first string assuming the current character won\'t be considered anymore.\n\t//cost to add.\n\tint addCount = 1 + function(s1, i, s2, j+1);//add 1 to the cost of adding a new character to the second string and compare it with the current character from string 1. \n```\n\nBased on the fact above, you could come up with the following recursive code:\n```\nprivate int helper(String s1,  int i, String s2, int j) {\n        if (i == s1.length()) {\n            //the first word came to an end.\n            return s2.length()-j;\n        } else if (j == s2.length()) {\n            return s1.length() - i;\n        } else if (s1.charAt(i) == s2.charAt(j)) {\n            return helper(s1, i+1, s2, j+1);            \n        }\n        else {\n            //replace.\n            int replaceCount = 1 + helper(s1, i+1, s2, j+1);\n            //delete.\n            int deleteCount = 1 + helper(s1, i+1, s2, j);\n            //add.\n            int addCount = 1 + helper(s1, i, s2, j+1);\n            return Math.min(replaceCount,Math.min(deleteCount, addCount));\n        }\n    }\n\t\t\nAnd, call it with helper(word1,0,word2,0).\n```\n\nThe above does exhaustive traversal causing an exponential time complexity. You could fix it to make O(m*n) by doing memoization and I won\'t discuss it here.\n\nDoing a bottoms-up DP requires us to think differently. You solve the first problem and then use that to solve the next problem. If you look at our recursive solution above, we are doing exactly the oppostive. We can\'t use the recursive equation as it is since our solution of the current stack depends on the next stack and DP requires us to think it in the opposite way. So we will rewrite our recursive equation to suit this need. Here is the code for that:\n\n```\n    private int helper_rec(String s1,  int i, String s2, int j) {\n        if (i < 0) {\n            //the first word came to an end.\n            return j+1;\n        } else if (j < 0) {\n            return i+1;\n        } else if (s1.charAt(i) == s2.charAt(j)) {\n            return helper_rec(s1, i-1, s2, j-1);            \n        }\n        else {\n            //replace.\n            int replaceCount = 1 + helper_rec(s1, i-1, s2, j-1);\n            //delete.\n            int deleteCount = 1 + helper_rec(s1, i-1, s2, j);\n            //add.\n            int addCount = 1 + helper_rec(s1, i, s2, j-1);\n            return Math.min(replaceCount,Math.min(deleteCount, addCount));\n        }\n    }\n```\n\nWe are now good. We are building the solution from the previous solution and this is what the DP requires. Now to use the DP, here is what we need to consider:\n1. Creating a 2-d array that may represent both words.\n2. Thinking about an index "0" that is always initialized with some value for both i and j.\n3. How to use the recursive condition from the above.\n\n```\n1. For the first part, just create an array with the size of those words.\nint[][] arr = new int[word1.length()+1][word2.length()+1];\n\n2. Initialization is a bit tricky but we could assume that the index \'0\' is basically an empty  string and how could we convert a string  to an empty string. Here is how we initialize that part:\n        //set the boundary conditions.\n        for (int i = 0; i<arr.length; i++) {\n            arr[i][0] = i; \n        }\n        \n        for (int j = 0; j<arr[0].length; j++) {\n            arr[0][j] = j; \n        }\n\t\t\t\t\n3. Using recursive condition: it is pretty much straight-foward:\n //replace.\n                    int replaceCount = 1 + arr[i-1][j-1];\n                    //delete.\n                    int deleteCount = 1 + arr[i-1][j]; \n                    //add.\n                    int addCount = 1 + arr[i][j-1];\n                    arr[i][j] =  Math.min(replaceCount,Math.min(deleteCount, addCount));\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\tThe above is an equivalent of our recursive equation where the position of the index is actually a subscript of an  array.\n\t\t\t\n\t\t\t\nThe only other thing to remember is when the characters match, we want to reuse the last known cost. That\'s if the characters match at arr[i][j], the new cost will be arr[i-1][j-1] since that will still apply to our next set of iterations.\n```\n\nHere is the working code for the above:\n```\n    public int minDistance(String word1, String word2) {\n        //return helper_rec(word1, word1.length()-1, word2, word2.length()-1);        \n        int[][] arr = new int[word1.length()+1][word2.length()+1];\n        //set the boundary conditions.\n        for (int i = 0; i<arr.length; i++) {\n            arr[i][0] = i; \n        }\n        \n        for (int j = 0; j<arr[0].length; j++) {\n            arr[0][j] = j; \n        }\n        \n         for (int i=1; i<=word1.length();i++){\n             for (int j=1; j<=word2.length() ;j++) {\n                 if (word1.charAt(i-1) != word2.charAt(j-1)) {\n                     //replace.\n                    int replaceCount = 1 + arr[i-1][j-1];\n                    //delete.\n                    int deleteCount = 1 + arr[i-1][j]; \n                    //add.\n                    int addCount = 1 + arr[i][j-1];\n                    arr[i][j] =  Math.min(replaceCount,Math.min(deleteCount, addCount));\n                 } else {\n                     arr[i][j] = arr[i-1][j-1];\n                 }\n             }\n         }   \n        \n        return arr[word1.length()][word2.length()];\n    }\n```\n\n\n\n\n
[]