Reach form Recursion to DP in simple change in code
Recursive Function - \n\n   int fun(string &s1, string &s2, int n, int m){\n        if(n == 0)                          // Base Case 1 : If first string is empt
**Recursive Function - **\n```\n   int fun(string &s1, string &s2, int n, int m){\n        if(n == 0)                          // Base Case 1 : If first string is empty return second string len. Because, we need to put all the characters from scratch\n            return m;                       //               string size convert first into second\n        else if(m == 0)\n                return n;                   // Base Case2 2: Vice-Versa of above base case\n        else if(s1[n - 1] == s2[m - 1])\n               return fun(s1, s2, n - 1, m - 1); //  when both characters are matched call the function for smaller input by reducing the size of both the strings\n        else               \n            return 1 + min({fun(s1,s2, n, m - 1), fun(s1, s2, n - 1, m), fun(s1, s2, n - 1, m - 1)});  // When characters Doesn\'t match we will perform all the 3 operations insert , delete , replace and give the minimum one.\n    } \n```\nNow let us try to convert the recursive code in dp - In Aditya Verma\'s style\uD83D\uDE0E\nreplace n with i and m with j in bottom-up dp. In initialization put the values of i and j.\n```\n    int minDistance(string str1, string str2) {\n        int n = str1.size();\n        int m = str2.size();\n        \n        int dp[n+1][m+1];                       //Initialization based on our base condition of recursion.\n        for(int i = 0 ; i<=n ; i++)\n            dp[i][0] = i;\n        for(int j = 0 ; j<=m ; j++)\n            dp[0][j] = j;\n\t\t\t\n\t\t\t//Inserting values in dp table- same as recursion condition.\n        \n        for(int i = 1 ; i<=n ; i++){\n            for(int j = 1 ; j<=m ; j++){\n                if(str1[i-1]==str2[j-1])\n                    dp[i][j] = dp[i-1][j-1];\n                else\n                    dp[i][j] = 1 + min({dp[i-1][j] , dp[i][j-1] , dp[i-1][j-1]});\n            }\n        }\n        \n        return dp[n][m];\n         }\n```
['Dynamic Programming', 'C++']