Recursion + dp
\nclass Solution {\npublic:\n    int solve(int i, int j, string s1, string s2, vector<vector<int>> &dp)\n    {\n        if(i == s1.length() && j == s2.length())
```\nclass Solution {\npublic:\n    int solve(int i, int j, string s1, string s2, vector<vector<int>> &dp)\n    {\n        if(i == s1.length() && j == s2.length()) return 0;\n        if(i == s1.length()) return s2.length()-j;\n        if(j == s2.length()) return s1.length()-i;\n        int &ans = dp[i][j];\n        if(ans != -1) return ans;\n        ans = INT_MAX;\n        if(s1[i] == s2[j])\n        {\n            ans = solve(i+1, j+1, s1, s2, dp);\n        }\n        else\n        {\n            ans = min(ans, solve(i, j+1, s1, s2, dp));\n            ans = min(ans, solve(i+1, j+1, s1, s2, dp));\n            ans = min(ans, solve(i+1, j, s1, s2, dp));\n            ans = ans + 1;\n        }\n        return ans;\n    }\n    int minDistance(string s1, string s2) {\n        vector<vector<int>> dp(1001, vector<int>(1001, -1));\n        return solve(0, 0, s1, s2, dp);\n    }\n};\n```
[]