[C++] Simple DP (Memoization) and Bottom-up with O(n) Space
Observation\nLet\'s imagine matching the characters of the string like a palindrome, from the begining and the end with 2 pointers i and j.\nWe may encounter 2 
**Observation**\nLet\'s imagine matching the characters of the string like a palindrome, from the begining and the end with 2 pointers `i` and `j`.\nWe may encounter 2 scenarios:\n1) The character at `i` matches character at `j`.\n2) The characters don\'t match each other\n\nIn case of 1 we just increase the pointer `i` and decrease the pointer `j`, `i++` and `j--` respectively.\n\nIn the second case we have 2 options:\n1) Insert one character at `j` to match the character at `i`.\n\nOr\n\n2) Insert one character at `i` to match the character at `j`.\n\nSince we are not actually adding the characters in the string but just calculating the cost,\nIn case 1 we increase the pointer `i` by `1` and `j` stays as it is, as we still need a character to match at `j`\nand in case 2 we decrease the pointer `j` by `1` and `i` stays as it is, as we still need a character to match at `i`.\nboth the cases adds cost `1` since we are inserting a letter.\n\nWe can then use these two different pairs of new `i` and `j` values (`i+1, j` and `i, j-1`) to again repeat the process and use the **minimum** result of these as our result for current pair of `i, j`.\nWe can see that this is recursive and thus we can use recursion with caching to store the repeated values.\n\n**Solution (Memoization)**\n```c++\nclass Solution {\npublic:\n    vector<vector<int>> memo;\n    int dp(string &s,int i,int j) {\n        if(i>=j)\t\t\t\t\t\t\t//Base case.\n            return 0;\n        if(memo[i][j]!=-1)\t\t\t\t\t//Check if we have already calculated the value for the pair `i` and `j`.\n            return memo[i][j];\n        return memo[i][j]=s[i]==s[j]?dp(s,i+1,j-1):1+min(dp(s,i+1,j),dp(s,i,j-1));\t\t//Recursion as mentioned above.\n    }\n    int minInsertions(string s) {\n        memo.resize(s.length(),vector<int>(s.length(),-1));\n        return dp(s,0,s.length()-1);\n    }\n};\n```\n**Complexity**\nSpace: `O(n^2)` as we can store at max all possible pairs of `i` and `j`.\nTime: `O(n^2)` as we calculate all pairs of possible `i` and `j`.\n\n**Note:** Space complexity can be reduced to `O(n)` by using bottom-up DP and storing only the previous state. (As we can see from the recursion, we only need `i-1` or `j-1` at any given point.)\n\n**Solution (Bottom-up)** \nAs I mentioned in the **Note** earlier, that we can reduce the space complexity as we only need the previous `i+1` or `j-1` states, I thought why not just add the solution as well. So here goes.\n\nWe can be cognizant of how we fill the `memo` table to optimize the space complexity when we have such scenarios. The code is pretty self explanatory with the added comments.\n```c++\nclass Solution {\npublic:\n    int minInsertions(string s) {\n        vector<int> memo(s.length(),0);\n        int prev,temp;\n        for(int i=s.length()-2;i>=0;i--) {\n            prev=0;                                          //This stores the value at memo[i+1][j-1];\n            for(int j=i;j<s.length();j++) {\n                temp=memo[j];                               //Get the value of memo[i+1][j].\n                memo[j]=s[i]==s[j]?prev:1+min(memo[j],memo[j-1]);     //memo[j]=memo[i+1][j], memo[j-1]=memo[i][j-1], prev=memo[i+1][j-1].\n                prev=temp;                        //Store the value of memo[i+1][j] to use it as memo[i+1][j-1] in the next iteration.\n            }\n        }\n        return memo[s.length()-1];\n    }\n};\n```\n**Complexity**\nSpace: `O(n)` as we reuse the previously stored value from previous state from the `memo` or `prev` variable.\nTime: `O(n^2)` as we calculate all pairs of possible `i` and `j`.
['Dynamic Programming', 'Memoization', 'C++']