[C++] Simple Recursive DP O(N^2)
This hard problem, is not that hard if we try to establish the recurrence relation. \nLet\'s say we start comparing the characters of the string, from both the 
This hard problem, is not that hard if we try to establish the recurrence relation. \nLet\'s say we start comparing the characters of the string, from both the ends i.e. `i` as starting index of string as `0` and `j` as ending index of string as `n-1`, where `n` is the length of the string.\nSo, the recurrence relation between the indices can be written as : \n\n```\nif s[i] == s[j]\n    DP(i, j) = DP(i + 1, j - 1)\notherwise,\n    DP(i, j) = 1 + min( DP(i + 1, j), DP(i, j - 1)) //Required to add a character, and see where addition gives minimum characters to insert\n```\nThen you can memoize the results in a matrix, for strings of large length. As here the sub-problems are overlapping. Or you can run an iterative DP length wise.\n\nTime complexity : `O(n^2)`, Space : `O(n^2)`\n```\nclass Solution {\npublic:\n    bool isPal(string s)\n    {\n        if(s.size() <= 1)\n            return 1;\n        for(int i = 0, j = s.size() - 1; i < j; i++,j--)\n        {\n            if(s[i] != s[j])\n                return 0;\n        }\n        return 1;\n    }\n    vector<vector<int>> dp;\n    int f(string &s, int i, int j)\n    {\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        {\n            dp[i][j] = f(s, i + 1, j - 1);   \n        }\n        else\n            dp[i][j] = min(f(s, i , j - 1), f(s, i + 1, j)) + 1;\n        \n        return dp[i][j];\n    }\n    \n    int minInsertions(string s) {\n        if(isPal(s))\n            return 0;\n        int n = s.size();\n        int i = 0, j = n - 1;\n        dp = vector<vector<int>> (n, vector<int>(n, - 1));\n        return f(s, i, j);\n    }\n};\n```
['Dynamic Programming', 'C']