From Brute Force to DP
Brute Force\n\nclass Solution {\n    public int minDistance(String word1, String word2) {\n        return minDistanceFrom(word1, word2, 0, 0);\n    }\n    priva
### Brute Force\n```\nclass Solution {\n    public int minDistance(String word1, String word2) {\n        return minDistanceFrom(word1, word2, 0, 0);\n    }\n    private int minDistanceFrom(String s1, String s2, int i1, int i2) {\n        if (i1 == s1.length()) // Inserts all the remaining characters of s2\n            return s2.length() - i2;\n\n        if (i2 == s2.length()) // Deletes all the remaining characters of s1\n            return s1.length() - i1;\n\n        if (s1.charAt(i1) == s2.charAt(i2)) {\n            return minDistanceFrom(s1, s2, i1 + 1, i2 + 1);\n        } else {\n            int dist1 = 1 + minDistanceFrom(s1, s2, i1 + 1, i2); // Deletes s1[i1] from s1\n            int dist2 = 1 + minDistanceFrom(s1, s2, i1, i2 + 1); // Inserts s2[i2] to s1\n            int dist3 = 1 + minDistanceFrom(s1, s2, i1 + 1, i2 + 1); // Replaces s1[i1] with s2[i2]\n\n            return Math.min(dist1, Math.min(dist2, dist3));\n        }\n    }\n}\n```\n### Top-down DP\nA two-dimensional array might be used to store results of all subproblems, in order to overcome overlapping subproblems.\n```\nclass Solution {\n    private Integer[][] dp;\n    public int minDistance(String word1, String word2) {\n        dp = new Integer[word1.length() + 1][word2.length() + 1];\n        return minDistanceFrom(word1, word2, 0, 0);\n    }\n    private int minDistanceFrom(String s1, String s2, int i1, int i2) {\n        if (i1 == s1.length()) // Inserts all the remaining characters of s2\n            return s2.length() - i2;\n\n        if (i2 == s2.length()) // Deletes all the remaining characters of s1\n            return s1.length() - i1;\n        \n        if (dp[i1][i2] != null)\n            return dp[i1][i2];\n        \n        if (s1.charAt(i1) == s2.charAt(i2)) {\n            return dp[i1][i2] = minDistanceFrom(s1, s2, i1 + 1, i2 + 1);\n        } else {\n            int dist1 = 1 + minDistanceFrom(s1, s2, i1 + 1, i2); // Deletes s1[i1] from s1\n            int dist2 = 1 + minDistanceFrom(s1, s2, i1, i2 + 1); // Inserts s2[i2] to s1\n            int dist3 = 1 + minDistanceFrom(s1, s2, i1 + 1, i2 + 1); // Replaces s1[i1] with s2[i2]\n\n            return dp[i1][i2] = Math.min(dist1, Math.min(dist2, dist3));\n        }\n    }\n}\n```\n### Bottom-up DP\n```\n    public int minDistance(String s1, String s2) {\n        int[][] dp = new int[s1.length() + 1][s2.length() + 1];\n\n        for (int i1 = 0; i1 <= s1.length(); i1++)\n            dp[i1][0] = i1;\n\n        for (int i2 = 0; i2 <= s2.length(); i2++)\n            dp[0][i2] = i2;\n\n        for (int i1 = 1; i1 <= s1.length(); i1++) {\n            for (int i2 = 1; i2 <= s2.length(); i2++) {\n                if (s1.charAt(i1 - 1) == s2.charAt(i2 - 1)) {\n                    dp[i1][i2] = dp[i1 - 1][i2 - 1];\n                } else {\n                    int dist1 = 1 + dp[i1 - 1][i2]; // Deletes s1[i1] from s1\n                    int dist2 = 1 + dp[i1][i2 - 1]; // Inserts s2[i2] to s1\n                    int dist3 = 1 + dp[i1 - 1][i2 - 1]; // Replaces s1[i1] with s2[i2]\n                    \n                    dp[i1][i2] = Math.min(dist1, Math.min(dist2, dist3));\n                }\n            }\n        }\n\n        return dp[s1.length()][s2.length()];\n    }\n```\n
[]