[C++] Intuition & Explanation Recursion To Iteration With Codes
INTUITION\n Rather than thinking of it from some other problem(LCS, which most have done), I feel that it is better to visualize it as a new problem. \n When tr
# INTUITION\n* Rather than thinking of it from some other problem(LCS, which most have done), I feel that it is better to visualize it as a new problem. \n* When trying to check if palindrome or building a palindrome, we start from start and end chars of string\n* If chars are same, we could change it to a subproblem from both sides.\n\t**f(i, j) = f(i + 1, j - 1)**\n* On the other hand, if they are different characters, we have 2 options. Either to **add a character at ith index = s[j] or add a character at jth index = s[i]**. The minimum of these two would give our required answer.\n\n\n```\n\t// Recursive Approach\n\tint f(string s, int i, int j, vector<vector<int>>& dp) {\n        if(i >= j)\n            return 0;\n        if(dp[i][j] != -1)\n            return dp[i][j];\n        if(s[i] == s[j])\n            return dp[i][j] = f(s, i + 1, j - 1, dp);\n        int op1 = 1 + f(s, i + 1, j, dp);\n        int op2 = 1 + f(s, i, j - 1, dp);\n        return dp[i][j] = min(op1, op2); \n    }\n```\t\n\t\n# \tRecursion To Iteration\n* Since, i is dependent on i + 1 (next value) and j on j - 1(previous value), then how can we write an iterative dp code?\n* We can see that we need to calculate our answer for smaller lengths first. We can precompute for len = 0 and then while increasing length, we will have our answer for all smaller length. Assume an index i, then j = i + len.\n\t\n  ``` \n    int minInsertions(string s) {\n        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 1e6));\n        int n = s.size();\n        for(int i = 0; i < n; i++)\n            dp[i][i] = 0;\n        for(int len = 1; len <= n; len++) {\n            for(int i = 0; i + len < n; i++) {\n                dp[i][i] = 0;\n                int j = i + len;\n                if(s[i] == s[j]) {\n                    if(len == 1)\n                        dp[i][j] = 0;\n                    else\n                        dp[i][j] = dp[i + 1][j - 1];\n                }\n                else {\n                    dp[i][j] = min(1 + dp[i + 1][j], 1 + dp[i][j - 1]);\n                }\n            }\n        }\n        return dp[0][n - 1];\n    }\n};\n```
[]