LPS | [ C++ ] | Recursion -> Memo -> Tabulation -> Space Optimization
Approach\nUsing the variant of Longest Common Subsequence, i,e Longest Pallindromic Subsequence find the length of LPS \n\nLPS as the name determine longest sub
# Approach\nUsing the variant of Longest Common Subsequence, i,e Longest Pallindromic Subsequence find the length of LPS \n\nLPS as the name determine longest subsequence in the string which is a pallindrome, so for the answer we just have to add the elements which are not included in the subsequence.\n\nBefore going to Solutions Please Solve these Questions: \n\n## Longest Common Subsequence :-\n  https://leetcode.com/problems/longest-common-subsequence/\n## Longest Pallindromic Subsequence :-\n https://leetcode.com/problems/longest-palindromic-subsequence/\n\n# Recursion +MEMO\n```\nclass Solution {\npublic:\n    int dp[501][501];\n    int lps(string& s, string& t, int i, int j) {\n        if(i >= s.size() || j >= t.size())\n            return 0;\n        if(dp[i][j] != -1)\n            return dp[i][j];\n        if(s[i] == t[j])\n            dp[i][j] = 1 + lps(s, t, i+1, j+1);\n        else\n            dp[i][j] = max(lps(s, t, i+1, j), lps(s, t, i, j+1));\n        return dp[i][j];\n    }\n    \n    int minInsertions(string s) {\n        memset(dp, -1, sizeof(dp));\n        string t = s;\n        reverse(t.begin(), t.end());\n        int l = lps(s, t, 0, 0);\n        return s.size() - l;\n    }\n};\n\n```\n# Tabulation\n```\nclass Solution {\npublic:\n    int lps(string s, string t){\n        int n = s.size();\n        int dp[n+1][n+1];\n        for(int i = 0 ;i<=n ; i++){\n            dp[0][i] = 0;\n        }\n          for(int j = 0 ;j<=n ; j++){\n            dp[j][0] = 0;\n        }\n        for(int i = 1;i<=n; i++){\n            for(int j = 1; j<=n; j++){\n                if(s[i-1] == t[j-1]){\n                    dp[i][j] = 1+dp[i-1][j-1];\n                }\n                else{\n                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);\n                }\n            }\n        }\n        return dp[n][n];\n    }\n    int minInsertions(string s) {\n        string t = s;\n        reverse(t.begin(), t.end());\n        int l = lps(s,t);\n        cout << l << endl;\n        return s.size() - l;  \n    }\n};\n```\n\n# Space Optimization\n```\nclass Solution {\npublic:\n    int minInsertions(string s) {\n        int n = s.size();\n        string t = s;\n        reverse(t.begin(), t.end());\n        int dp[n+1];\n        memset(dp, 0, sizeof(dp));\n        int prev = 0;\n        for(int i = 1; i <= n; i++) {\n            prev = dp[0];\n            for(int j = 1; j <= n; j++) {\n                int temp = dp[j];\n                if(s[i-1] == t[j-1])\n                    dp[j] = 1 + prev;\n                else\n                    dp[j] = max(dp[j-1], dp[j]);\n                prev = temp;\n            }\n        }\n        return n - dp[n];\n    }\n};\n\n```
['String', 'Dynamic Programming', 'Recursion', 'Memoization', 'C++']