100% memory efficient and 98% faster solution.[EASY] | [C++] | [DP] | [LCS]
TOP-DOWN DYNAMIC PROGRAMING\nWe need to find if there exist any subsequence of string S1 which is palindrome. \nIf there is such a subsequence sub, then we need
**TOP-DOWN DYNAMIC PROGRAMING**\nWe need to find if there exist any subsequence of string **S1** which is palindrome. \nIf there is such a subsequence **sub**, then we need minimum ***len(S1)-len(sub)***\nElse, we need atleast ***len(S1)*** number of insertions to make it palindrome.\n\nTo find the len of subsequence of S1 which is palindrome, we can use [Longest Common Subsequence](https://en.wikipedia.org/wiki/Longest_common_subsequence_problem). \n```\nint minInsertions(string s1) {\n        int n = s1.size();\n        int DP[n+1][n+1];\n        string s2  =s1;\n        reverse(s1.begin(),s1.end());\n        \n        for(int i=0;i<=n;i++){\n            for(int j=0;j<=n;j++){\n                if(i==0 || j==0){\n                    DP[i][j] = 0;\n                }\n                else if(s1[i-1]==s2[j-1]){\n                    DP[i][j] = DP[i-1][j-1]+1;\n                }\n                else{\n                    DP[i][j] = max(DP[i-1][j],DP[i][j-1]);\n                }\n            }\n        }\n    \n        return n-DP[n][n];\n    }\n```\n\nPlease upvote if you liked the post.\nYou can refer to the [this](https://www.youtube.com/watch?v=AEcRW4ylm_c&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=33&t=0s) link if you want detail explanation.
['Dynamic Programming', 'C']