java 7m dp solution with detailed explanation
we use a array dist to save the minimum distance of substring of word1 and word2, i.e., dist[i][j] denotes the minimum distance of word1.substring(0, i) and wor
we use a array ```dist``` to save the minimum distance of substring of ```word1``` and ```word2```, i.e., ```dist[i][j]``` denotes the minimum distance of ```word1.substring(0, i)``` and ```word2.substring(0, j)```.\nApparently, ```dist[0][j] = j``` and ```dist[i][0] = i```.\nWhen we calculate ```dist[i][j]```, we first compare ```word1[i]``` and ```word2[j]```, if ```word1[i]``` equals ```word2[j]```, then ```dist[i][j]``` equals ```dist[i - 1][j - 1]```. If ```word1[i] != word2[j]```, then we have three operations:\n1. replace word1[i] with word2[j] (```dist[i - 1][j - 1] + 1```)\n2. delete word1[i] (```dist[i - 1][j] + 1```)\n3. delete word2[j] (```dist[i][j - 1] + 1```)\n\nNote that insert and delete are symmetric operations, so we choice 2 is equal to insert character to word2 and choice 3 is equal to insert character to word1.\n```\npublic int minDistance(String word1, String word2) {\n\tint dist[][] = new int[word1.length() + 1][word2.length() + 1];\n\tfor(int i = 0; i < word1.length(); i++) \n\t\tdist[i + 1][0] = i + 1;\n\tfor(int i = 0; i < word2.length(); i++)\n\t\tdist[0][i + 1] = i + 1;\n\tfor(int i = 0; i < word1.length(); i++) {\n\t\tfor(int j = 0; j < word2.length(); j++) {\n\t\t\tif( word1.charAt(i) == word2.charAt(j) )\n\t\t\t\tdist[i + 1][j + 1] = dist[i][j];\n\t\t\telse\n\t\t\t\tdist[i + 1][j + 1] = Math.min(Math.min(dist[i][j + 1], dist[i + 1][j]) + 1, dist[i][j] + 1);\n\t\t}\n\t}\n\treturn dist[word1.length()][word2.length()];\n}\n```
['Dynamic Programming', 'Java']