C++ DP Solution (Recursive, Memorization, Tabulation, Space-Optimized to single 1D array)
Recursive\n\nclass Solution {\npublic:\n    int solve(int i, int j, string &s1, string &s2){\n        //Base Case\n        if(i<0) return j + 1;\n        if(j<0
### Recursive\n```\nclass Solution {\npublic:\n    int solve(int i, int j, string &s1, string &s2){\n        //Base Case\n        if(i<0) return j + 1;\n        if(j<0) return i + 1;\n        if(s1[i]==s2[j]) return solve(i-1,j-1,s1,s2);\n        \n        //Insert the matching character so reduce the j no effect on i due to insertion\n        int ins = solve(i,j-1,s1,s2); \n        \n        // Delete the character so reduce the i but no effect on j\n        int del = solve(i-1,j,s1,s2); \n        \n        // Replace with matching character so reduce i and j both\n        int rep = solve(i-1,j-1,s1,s2);\n        \n        return 1 + min({ins, del, rep});\n    }\n    \n    int minDistance(string s1, string s2) {\n        int m = s1.size(), n = s2.size();\n        return solve(m,n,s1,s2);\n    }\n};\n```\n\n### Memorization\n```\nclass Solution {\npublic:\n    int solve(int i, int j, string &s1, string &s2,vector<vector<int>> &dp){\n        //Base Case\n        if(i<0) return j + 1;\n        if(j<0) return i + 1;\n        if(dp[i][j] != -1) return dp[i][j];\n        if(s1[i]==s2[j]) return dp[i][j] = solve(i-1,j-1,s1,s2, dp);\n        \n        //Insert the matching character so reduce the j no effect on i due to insertion\n        int ins = solve(i,j-1,s1,s2, dp); \n        \n        // Delete the character so reduce the i but no effect on j\n        int del = solve(i-1,j,s1,s2, dp); \n        \n        // Replace with matching character so reduce i and j both\n        int rep = solve(i-1,j-1,s1,s2, dp);\n        \n        return dp[i][j] = 1 + min({ins, del, rep});\n    }\n    \n    int minDistance(string s1, string s2) {\n        int m = s1.size(), n = s2.size();\n        vector<vector<int>> dp(m, vector<int>(n,-1));\n        return solve(m-1,n-1,s1,s2,dp);\n    }\n};\n```\n\n### Tabulation\n```\n// Used 1-Based Indexing\nclass Solution {\npublic:    \n    int minDistance(string s1, string s2) {\n        int m = s1.size(), n = s2.size();\n        vector<vector<int>> dp(m+1, vector<int>(n+1));\n        \n        //Base Case\n        for(int j=0;j<=n;j++) dp[0][j] = j;\n        for(int i=0;i<=m;i++) dp[i][0] = i;\n        \n        for(int i=1;i<=m;i++){\n            for(int j=1;j<=n;j++){\n                if(s1[i-1]==s2[j-1]) dp[i][j] = dp[i-1][j-1];\n                else{\n                    int ins = dp[i][j-1];\n                    int del = dp[i-1][j];\n                    int rep = dp[i-1][j-1];\n                    dp[i][j] = 1 + min({ins, del, rep});\n                }\n            }\n        }\n        return dp[m][n];\n    }\n};\n```\n\n### Space-Optimized\n```\nclass Solution {\npublic:    \n    int minDistance(string s1, string s2) {\n        int m = s1.size(), n = s2.size();\n        vector<vector<int>> dp(m+1, vector<int>(n+1));\n        vector<int> prev(n+1), cur(n+1);\n        \n        for(int i=0;i<=m;i++){\n            for(int j=0;j<=n;j++){\n                if(i==0) cur[j] = j;\n                else if(j==0) cur[j] = i;\n                else if(s1[i-1]==s2[j-1]) cur[j] = prev[j-1];\n                else{\n                    int ins = cur[j-1];\n                    int del = prev[j];\n                    int rep = prev[j-1];\n                    cur[j] = 1 + min({ins, del, rep});\n                }\n            }\n            prev = cur;\n        }\n        return prev[n];\n    }\n};\n```\n\n### Further Optimized\n```\nclass Solution {\npublic:    \n    int minDistance(string s1, string s2) {\n        int m = s1.size(), n = s2.size();\n        vector<vector<int>> dp(m+1, vector<int>(n+1));\n        vector<int> prev(n+1);\n        int topLeft, top, left;\n        for(int i=0;i<=m;i++){\n            for(int j=0;j<=n;j++){\n                if(i==0) left = j;\n                else if(j==0) left = i;\n                else{\n                    top = prev[j];\n                    if(s1[i-1]==s2[j-1]) left = topLeft;\n                    else left = 1 + min({topLeft, top, left});   \n                }\n                topLeft = prev[j];\n                prev[j] = left;\n            }\n        }\n        return prev[n];\n    }\n};\n```\n#### Please Upvote if you like the solution and comment your queries
['Dynamic Programming', 'C']