[C++] Three Solutions - Recursion, Top-Down, Bottom-Up - DP
Recursive Solution\nTime Complexity - O (3 ^ max(a, b))\nSpace Complexity - O (1)\n\n\nint minDist(string a, string b, int i, int j) {\n        if (i == -1) {\n
**Recursive Solution\nTime Complexity - O (3 ^ max(a, b))\nSpace Complexity - O (1)**\n\n```\nint minDist(string a, string b, int i, int j) {\n        if (i == -1) {\n            return j + 1;\n        }\n        if (j == -1) {\n            return i + 1;\n        }\n        if (a[i] == b[j]) {\n            return minDist(a, b, i - 1, j - 1);\n        }\n        else {\n            int add = minDist(a, b, i, j - 1);\n            int replace = minDist(a, b, i - 1, j - 1);\n            int remove = minDist(a, b, i - 1, j);\n            \n            return 1 + min(min(add, replace), remove);\n        }\n    }\n```\n\n<br>\n<hr>\n<br>\n\n**Top Down DP Solution**\n\n```\nint minDist(string a, string b, int i, int j, vector <vector <int>> dp) {\n        if (i == -1) {\n            return j + 1;\n        }\n        if (j == -1) {\n            return i + 1;\n        }\n        if (dp[i][j] != -1) {\n            return dp[i][j];\n        }\n        if (a[i] == b[j]) {\n            dp[i][j] =  minDist(a, b, i - 1, j - 1, dp);\n            return dp[i][j];\n        }\n        else {\n            int add = minDist(a, b, i, j - 1, dp);\n            int replace = minDist(a, b, i - 1, j - 1, dp);\n            int remove = minDist(a, b, i - 1, j, dp);\n            \n            dp[i][j] =  1 + min(min(add, replace), remove);\n            return dp[i][j];\n        }\n    }\n```\n\n<br>\n<hr>\n<br>\n\n**Bottom Up DP Solution\nTime Complexity - O (a * b)\nSpace Complexity - O (a * b)**\n\n```\nint minDist(string a, string b) {\n        vector <vector <int>> dp(a.length() + 1, vector <int>(b.length() + 1, -1));\n        \n        for (int i = 0; i < a.length() + 1; i++) {\n            for (int j = 0; j < b.length() + 1; j++) {\n                if (i == 0) {\n                    dp[i][j] = j;\n                }\n                else if (j == 0) {\n                    dp[i][j] = i;\n                }\n                else {\n                    if (a[i - 1] == b[j - 1]) {\n                        dp[i][j] = dp[i - 1][j - 1];\n                    }\n                    else {\n                        int add = dp[i][j - 1];\n                        int replace = dp[i- 1][j - 1];\n                        int remove = dp[i - 1][j];\n                        \n                        dp[i][j] = 1 + min(min(add, replace), remove);\n                    }\n                }\n            }\n        }\n        \n        return dp[a.length()][b.length()];\n    }\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C', 'C++']