[Python] Recursive -> Memoization -> Tabular DP with Detailed Explanation
\n\n\n\n\n\nRecursive:\n\nclass Solution:\n    def minDistance(self, w1: str, w2: str) -> int:\n        def solve(w1, w2, n, m): \n            # Base Case if an
![image](https://assets.leetcode.com/users/images/ebd26aeb-c4c8-45bd-90cb-1d01670b37b9_1655779370.086117.jpeg)\n![image](https://assets.leetcode.com/users/images/8114c2a7-9765-4868-a01c-76eccc8d6c0f_1655779380.6150026.jpeg)\n![image](https://assets.leetcode.com/users/images/fbf87ad1-e78e-4e9c-9c5f-d4b95385bf98_1655779388.4014256.jpeg)\n\n\n\n**Recursive**:\n```\nclass Solution:\n    def minDistance(self, w1: str, w2: str) -> int:\n        def solve(w1, w2, n, m): \n            # Base Case if any one of w1 or w2 is empty \n            if n == 0 or m == 0: return m or n\n            \n            elif w1[n-1] == w2[m-1]:\n                return solve(w1, w2, n-1, m-1)\n            \n            else:\n                return 1 + min(\n                                solve(w1, w2, n-1, m-1),  # Replace\n                                solve(w1, w2, n-1, m),    # Delete\n                                solve(w1, w2, n, m-1)     # Insert\n                                )\n        \n        return solve(w1, w2, len(w1), len(w2))\n    \n\n# Time Limit Exceeded\n# We need to use Memoization in this Solution to avoid repetative same calculation of sub-problems\n```\n\n**Memoization**:\n```\nclass Solution:\n    def minDistance(self, word1: str, word2: str) -> int:\n        memo = {}\n        \n        def dfs(i, j):\n            if i == 0 or j == 0: return j or i\n                        \n            if (i,j) in memo:\n                return memo[(i,j)]\n            \n            if word1[i-1] == word2[j-1]:\n                ans = dfs(i-1, j-1)\n            else: \n                ans = 1 + min(dfs(i, j-1), dfs(i-1, j), dfs(i-1, j-1))\n                \n            memo[(i,j)] = ans\n            return memo[(i,j)]\n        \n        return dfs(len(word1), len(word2))\n\t\t\n# Time: O(N^2)\n# Space: O(N^2)\n```\n\n\n**Tabular DP**:\n```\nclass Solution:\n    def minDistance(self, w1: str, w2: str) -> int:\n        n = len(w1); m = len(w2)\n        \n        dp = [[0]*(m+1) for i in range(n+1)]\n        \n        for j in range(m+1): # Base Case 0th row where len(w1) = 0\n            dp[0][j] = j\n        \n        for i in range(n+1): # Base Case 0th column where len(w2) = 0\n            dp[i][0] = i\n        \n        for i in range(1, n+1):\n            for j in range(1, m+1):\n                if w1[i-1] == w2[j-1]:\n                    dp[i][j] = dp[i-1][j-1]\n                else:\n                    dp[i][j] = 1 + min(\n                                        dp[i-1][j-1],  # Replace \n                                        dp[i-1][j],    # Delete\n                                        dp[i][j-1]     # Insert\n                                        )\n        \n        return dp[-1][-1]\n\t\t\n# Time: O(N^2)\n# Space: O(N^2)\n```\n\nAll Concepts of DP: **https://github.com/SamirPaul1/DSAlgo/tree/main/02_Dynamic-Programming**
['Dynamic Programming', 'Recursion', 'Memoization', 'Python', 'Python3']