✅ C++ simple code | Recursive + Memoization | Top-Down approach | Runtime : 4ms
if you like my approach don\'t forget to hit upvote button ! : )\n\nclass Solution {\npublic:\n    /*\n    \n        There are a lot of these types of questions
**if you like my approach don\'t forget to hit upvote button ! : )**\n```\nclass Solution {\npublic:\n    /*\n    \n        There are a lot of these types of questions in DP Hard. If you learn to recognize the basic structure, you can come up with an answer fairly quickly.\n        Couple words that give away the DP nature of the problem\n\n        1.Palindrome\n        2.Minimum\n        \n        If we break the question apart we get:\n\n        1.How many changes do I need to perform to make S.substring(i, j) to a palindrome.\n        2.How many ways can I split the string from i to j into groups and what are their costs.\n        3.What is the minimum combination of these groups.\n    \n        First thing you should make is a map that contains all the cost from i to j\n        This is faily simple given the nature of substituion.\n    */\n    int pal[101][101];\n    int dp[101][101];\n    int palindromePartition(string s, int k) {\n        \n        \n        // STEP-1\n        // Leetcode problem -> https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/\n        // For each substring calculate the minimum number of steps to make it \n        // palindrome and store it in a table.\n        memset(pal,0,sizeof(pal));\n        int n=s.length();\n        // generate all substrings\n        for(int g=0;g<n;g++)\n        {\n            for(int i=0,j=g; j<n; i++,j++)\n            {\n                \n                if(g==0){\n                    pal[i][j]=0;// 0 steps required to make it palindrome\n                }\n                else if(g==1){\n                    if(s[i] == s[j])\n                        pal[i][j]=0;\n                    else\n                        pal[i][j]=1;\n                }\n                else\n                {\n                    if(s[i] == s[j]){\n                        pal[i][j] = pal[i+1][j-1];\n                    }\n                    else{\n                        //1 step extra required to make string palindrome\n                        // dry run on "leetcode" string with \'gap=3\' \n                        \n                        // instead of this --> pal[i][j] = min(pal[i+1][j], pal[i][j-1]) + 1; \n                        pal[i][j] = pal[i+1][j-1] + 1; \n                    }\n                }\n            }\n        }\n        \n        // for(int i=0;i<n;i++){\n        //     for(int j=0;j<n;j++){\n        //         cout<<pal[i][j]<<"  ";\n        //     }\n        //     cout<<endl;\n        // }\n        \n        memset(dp,-1,sizeof(dp));\n        return findMinCost(0, k, n); // find minimum cost by partition\n        \n    }\n    \n    // similar to MCM (matrix chain multiplication)\n    int findMinCost(int index, int k, int n)\n    {\n        \n        if(index==n){\n\t\t\t\treturn n; // max value  -- isse jyada insertion nahi hoga = min steps required to \n                            // make string palindrome\n\t\t}\n        \n        if(k==1){  // if single non-empty substring, then minimum no. of steps required to make it palindrome\n            return pal[index][n-1];\n        }\n        \n        // memoization\n        if(dp[index][k]!=-1)\n            return dp[index][k];\n        \n        int ans=INT_MAX;\n        for(int i=index;i<n;i++){\n            \n            ans = min(ans, pal[index][i] + findMinCost(i+1, k-1, n));\n        }\n        \n        dp[index][k]=ans;\n        return ans;\n    }\n};\n```
['Recursion', 'Memoization', 'C', 'C++']