C++ Easiest Solution With Detailed Explanation
class Solution {\npublic:\n    //First of all create a 3-D dp array//\n    \n    int dp[101][101][101];\n    \n    int check(string s,int start,int end){\n     
class Solution {\npublic:\n    //First of all create a 3-D dp array//\n    \n    int dp[101][101][101];\n    \n    int check(string s,int start,int end){\n        \n        int ans=0;\n        \n        while(start<end){\n            if(s[start++]!=s[end--]){\n                ans++;\n            }\n        }\n        \n        return ans;\n        \n    }\n    \n    \n    int helper(string s,int k,int start,int end){\n        \n    //All Edge cases are handled here\n        \n    //If the end pointer less than the starting pointer then there is nothing to proceed further\n        \n    if(end<start){\n        \n        //Now if number of cuts required is zero then ans will be zero\n        \n        if(k<=0){\n            return 0;\n        }\n        \n        //Otherwise its an invalid option\n        \n        else{\n            return 99999;\n        }\n        \n    }\n        \n        //If the length of the string and number of the parts are same then also answer will be zero\n        \n        if(end-start+1==k){\n            return 0;\n        }\n        \n        //If length of the string is less than the requires parts of the string then it gonna also an invalid option return big value for invalidity\n        \n        if(end-start+1<k){\n            return 99999;\n        }\n        \n        //If required part of the string is 1 then determine how many character change is required to make the string from start to end be palindrome\n        \n        \n        if(k==1){\n            int a=check(s,start,end);\n            dp[start][end][k]=a;\n            return a;\n        }\n        \n        //If we already got the answer for a paricular start,end,k then there is no need to determine it again \n        \n        \n        if(dp[start][end][k]!=-1){\n            return dp[start][end][k];\n        }\n        \n        int ans=99999;\n        \n        \n     // If above all the cases are not matched then comes down to our final logic\n        \n        \n        for(int i=start;i<=end;i++){\n            \n            //For a particular position determine how many cuts are required to make the left most part palindrome and same for the rightmost part.\n            \n            \n            int a=helper(s,1,start,i);\n            int b=helper(s,k-1,i+1,end);\n            \n            //Find out minimum answer \n            \n            ans=min(ans,a+b);\n            \n        }\n        \n        //Store the value in predefined dp array\n        \n        \n        dp[start][end][k]=ans;\n        return ans;\n      \n        \n    }\n    \n    int palindromePartition(string s, int k) {\n        \n        //Initialize the dp array with -1 using memset\n        \n        memset(dp,-1,sizeof(dp));\n               \n        //Call the helper functiion \n        \n        return helper(s,k,0,s.length()-1);\n        \n    }\n};
[]