DP | 4 Approaches | Recursion , Memoization, Tabulation and Space Optimization
Approach 1 : Recursion\n\n\nint solve(int i, int j, string &str1, string &str2){     \n        if(j<0){\n            return i+1;\n        }\n        if(i<0){\n 
**Approach 1 : Recursion**\n\n```\nint solve(int i, int j, string &str1, string &str2){     \n        if(j<0){\n            return i+1;\n        }\n        if(i<0){\n            return j+1;\n        }\n        if(str1[i]==str2[j]){\n            return solve(i-1,j-1,str1,str2);\n        }\n        else{\n            int insert = 1 + solve(i,j-1,str1,str2);\n            int deleted = 1 + solve(i-1,j,str1,str2);\n            int replace = 1 + solve(i-1,j-1,str1,str2);\n            return min(min(insert,deleted),replace);\n        }\n    }\n    \n    int minDistance(string word1, string word2) {\n        int n = word1.size();\n        int m = word2.size();\n        return solve(n-1,m-1,word1,word2);\n    }\n```\n\nTime : exponential\nSpace : O(m+n) for stack space     => m = word1.size() and n = word2.size()\n\n**Approach 2 : Memoization**\n\n```\nint solve(int i, int j, string &str1, string &str2, vector<vector<int>>&dp){     \n        if(j<0){\n            return i+1;\n        }\n        if(i<0){\n            return j+1;\n        }\n        if(dp[i][j]!=-1){\n            return dp[i][j];\n        }\n        if(str1[i]==str2[j]){\n            return dp[i][j] = solve(i-1,j-1,str1,str2,dp);\n        }\n        else{\n            int insert = 1 + solve(i,j-1,str1,str2,dp);\n            int deleted = 1 + solve(i-1,j,str1,str2,dp);\n            int replace = 1 + solve(i-1,j-1,str1,str2,dp);\n            return dp[i][j] = min(min(insert,deleted),replace);\n        }\n    }\n    \n    int minDistance(string word1, string word2) {\n        int n = word1.size();\n        int m = word2.size();\n        vector<vector<int>>dp(n,vector<int>(m,-1));\n        return solve(n-1,m-1,word1,word2,dp);\n    }\n```\n\nTime : O(m.n)   => m = word1.size() and n = word2.size()\nSpace : O(m+n) stack space and O(m.n)  for dp space\n\n**Approach 3 : Tabulation**\n\n```\n       int minDistance(string word1, string word2) {\n        int n = word1.size();\n        int m = word2.size();\n        vector<vector<int>>dp(n+1,vector<int>(m+1,0));\n       \n        for(int i=0;i<n+1;i++){\n            dp[i][0]=i;\n        }\n        for(int j=1;j<m+1;j++){\n            dp[0][j]=j;\n        }\n       \n        for(int i=1;i<n+1;i++){\n            for(int j=1;j<m+1;j++){\n                if(word1[i-1]==word2[j-1])\n                    dp[i][j] = dp[i-1][j-1];\n                else{\n                    int insert = 1 + dp[i][j-1];\n                    int deleted = 1 + dp[i-1][j];\n                    int replace = 1 + dp[i-1][j-1];\n                    dp[i][j] = min(min(insert,deleted),replace);                    \n                }        \n            }\n        }\n        return dp[n][m];\n    }\n```\n\nTime : O(m.n)   => m = word1.size() and n = word2.size()\nSpace : O(m.n)  for dp space\n\n**Approach 4 : Space optimized to O(m) **\n\n```\n     int minDistance(string word1, string word2) {\n        int n = word1.size();\n        int m = word2.size();\n        vector<int>prev(m+1,0),curr(m+1,0);\n        \n        for(int i=0;i<m+1;i++){\n            prev[i]=i;\n        }\n        for(int i=1;i<n+1;i++){\n            curr[0] = i;\n            for(int j=1;j<m+1;j++){\n                if(word1[i-1]==word2[j-1])\n                    curr[j] = prev[j-1];\n                else{\n                    int insert = 1 + curr[j-1];\n                    int deleted = 1 + prev[j];\n                    int replace = 1 + prev[j-1];\n                    curr[j] = min(min(insert,deleted),replace);                    \n                }        \n            }\n            prev = curr;\n        }\n        \n        return prev[m];\n    }\n```\n\nTime : O(m.n)   => m = word1.size() and n = word2.size()\nSpace : O(m)  for dp \n\n\n
['Dynamic Programming', 'Recursion', 'Memoization']