[C++] - Top-down and Bottom-up approaches
Top Down Approach:\n\nclass Solution {\npublic:\n    int solve(string &str,int low,int high,vector<vector<int> > &dp){\n        if(low>high)\n            return
**Top Down Approach:**\n```\nclass Solution {\npublic:\n    int solve(string &str,int low,int high,vector<vector<int> > &dp){\n        if(low>high)\n            return 0;\n        if(dp[low][high]!=-1)\n            return dp[low][high];\n        if(low==high){\n            return dp[low][high]=0;\n        }\n        if(str[low]==str[high]){\n            return dp[low][high]=solve(str,low+1,high-1,dp);\n        }\n        return dp[low][high]=min(solve(str,low+1,high,dp),solve(str,low,high-1,dp))+1;\n    }\n    int minInsertions(string s) {\n        int n=s.length();\n        int index1=0,index2=n-1;\n        if(index1>=index2)\n            return 0;\n        vector<vector<int> > dp(n,vector<int>(n,-1));\n        return solve(s,index1,index2,dp);\n    }\n};\n```\n**Bottom Up Approach:**\n```\nclass Solution {\npublic:\n    int minInsertions(string str) {\n        int n=str.length();\n        int index1=0,index2=n-1;\n        if(index1>=index2)\n            return 0;\n        vector<vector<int> > dp(n,vector<int>(n,-1));\n        //dp[i][j]=no of insertions to make str[i...j] palindrome\n        for(int i=0;i<n;i++){\n            dp[i][i]=0;\n        }\n        for(int i=0;i<n-1;i++){\n            if(str[i]==str[i+1])\n                dp[i][i+1]=0;\n            else\n                dp[i][i+1]=1;\n        }\n        for(int i=2;i<n;i++){\n            for(int j=0;j<n-i;j++){\n                int k=i+j;\n                if(str[j]==str[k])\n                    dp[j][k]=dp[j+1][k-1];\n                else\n                    dp[j][k]=min(dp[j][k-1],dp[j+1][k])+1;\n            }\n        }\n        return dp[0][n-1];\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'C', 'C++']