Dyanmic Programming Beats 90% solution with detailed explanation
The question requires us to breakdown the problem in terms of smaller sub-problem\n\nLet dp be a matrix where dp[i][j] stores the minimum number of insertions r
The question requires us to breakdown the problem in terms of smaller sub-problem\n\nLet dp be a matrix where dp[i][j] stores the minimum number of insertions required to make subtring [i...j] palindromic \n  Case -1 s[i] != s[j]\n              in this case we have two choices, add a character equal to s[i] at the position of jth index and now the i and j be will equal ,which will cost us 1  move, the rest can be calculated for smaller subproblem [i+1, ...,j] .\n\t\t\t  similarly we can do by adding a character equal to s[j] at the position of ith index and calculate [i,j-1]\n\t\t\t  Recurrence Relation -dp[i][j] =min(dp[i+1][j],dp[i][j-1]) +1\n\tCase-2 s[i] ==s[j]\n\t  In this case apart from from the above ways we can derive answer, our answer can also be gained by finding out moves to make [i+1,...,j-1] palindromic\n\t   Recurrence Relation dp[i][j]=min(dp[i+1][j-1],min(dp[i+1][j],dp[i][j-1])+1)\n\t   \n\t   \n\t   Code ->\n\t    int minInsertions(string s) {\n     \n        int n=s.size();\n        int dp[n][n];\n        memset(dp,0,sizeof dp);\n        \n        for(int l=2;l<=n;l++)\n        {\n            for(int i=0;i<n-l+1;i++)\n            {\n                int j=i+l-1;\n                if(j==(i+1))\n                {\n                    if(s[j]==s[i])\n                        dp[i][j]=0;\n                    else\n                        dp[i][j]=1;\n                }\n                else\n                {\n                    dp[i][j]=INT_MAX;\n                    if(s[i]==s[j])\n                        dp[i][j]=dp[i+1][j-1];\n                    \n                    dp[i][j]=min(dp[i][j],min(dp[i+1][j],dp[i][j-1])+1);\n                }\n            }\n        }\n        return dp[0][n-1];\n        \n    }
[]