How (len -  LPS)??? Explained with images || Recursion to Bottom UP
\n\n\n\n## RECURSION\n\nclass Solution {\npublic:\n    int lps(string& s, int start, int end)\n    {\n        if (start == end) return 1;\n        if (start > e
![image](https://assets.leetcode.com/users/images/84f65bac-e8cd-4634-bf72-0b7685762631_1682124024.6771638.jpeg)\n![image](https://assets.leetcode.com/users/images/ad5faf88-fff6-4085-93a8-82ee9b1e28d6_1682124031.7868736.jpeg)\n\n\n## RECURSION\n```\nclass Solution {\npublic:\n    int lps(string& s, int start, int end)\n    {\n        if (start == end) return 1;\n        if (start > end) return 0;\n        \n        if (s[start] == s[end]) return (2 + lps(s, start + 1, end - 1));\n        int leaveLeft = lps(s, start + 1, end);\n        int leaveRight = lps(s, start, end - 1);\n        return max(leaveLeft, leaveRight);\n    }\n    int minInsertions(string s) \n    {\n        int lpsLen = lps(s, 0, s.size() - 1);\n        return (s.size() - lpsLen);\n    }\n\n};\n```\n//=======================================================================================================================\n## TOP-DOWN\n```\nclass Solution {\npublic:\n    int lps(string& s, vector<vector<int>>&dp, int start, int end)\n    {\n        if (start == end) return 1;\n        if (start > end) return 0;\n        if (dp[start][end] != -1) return dp[start][end];\n        \n        if (s[start] == s[end]) return (2 + lps(s, dp, start + 1, end - 1)); //directly return \n        \n        int leaveLeft = lps(s, dp, start + 1, end);\n        int leaveRight = lps(s, dp, start, end - 1);\n        return dp[start][end] = max(leaveLeft, leaveRight); //store the ans\n    }\n    int minInsertions(string s) \n    {\n        int n = s.size();\n        vector<vector<int>>dp(n, vector<int>(n, -1));\n        int lpsLen = lps(s, dp, 0, n - 1);\n        return (n - lpsLen);\n    }\n\n};\n```\n//=======================================================================================================================\n## BOTTOM-UP\n```\nclass Solution {\npublic:\n    int lps(string& s)\n    {\n       int n = s.size();\n        vector<vector<int>>dp(n, vector<int>(n, 0));\n        //for n length string we need LPS for string with length (n - 1) or (n - 2)\n        //We need to already have LPS for smaller lengths before moving to greater lengths\n        //so we need to go bottom up \n        //Calculating LPS for all strings of length = 1 to length = n\n        //================================================================================\n        for (int len = 1; len <= n; len++)\n        {\n            for (int start = 0; start <= (n - len); start++)\n            {\n                int end = start + len - 1; //[start, end] denotes the string under consideration\n                if (len == 1) { dp[start][end] = 1; continue; }\n                \n                if (s[start] == s[end]) dp[start][end] = 2 + dp[start + 1][end - 1];\n                else dp[start][end] = max(dp[start + 1][end], dp[start][end - 1]); \n            }\n        }\n        //=====================================================================================\n        return dp[0][n - 1];\n    }\n    int minInsertions(string s) \n    {\n        int n = s.size();\n        int lpsLen = lps(s);\n        return (n - lpsLen);\n    }\n\n};\n```
['Dynamic Programming', 'C', 'C++']