straightforward c++ solution from O(KN^3) to O(KN^2)
subproblem dp[l,k] represents the min cost for string length l (from begining) with k pal-parts.\nthen dp[i,k]=min(dp[j, k-1]+cost(j,i),dp[i,k])\ncpp\n    int p
subproblem dp[l,k] represents the min cost for string length l (from begining) with k pal-parts.\nthen dp[i,k]=min(dp[j, k-1]+cost(j,i),dp[i,k])\n```cpp\n    int palindromePartition(string s, int k) {\n        //min cuts to make it palindrome?\n        int n=s.size();\n        vector<vector<int>> dp(n+1,vector<int>(k+1,n)); //min replace length of string with k parts\n        dp[0][0]=0;\n        for(int i=1;i<=n;i++){ //length \n            for(int j=1;j<=k;j++){ //number of pal groups\n                for(int l=i-1;l>=0;l--) //start \n                {\n                    int d=cost(s,l,i-1);\n                    dp[i][j]=min(dp[l][j-1]+d,dp[i][j]);\n                }\n            }\n        }\n        return dp[n][k];\n    }\n    int cost(string s,int start,int end){\n        int ans=0;\n        while(start<end){\n            if(s[start++]!=s[end--]) ans++;\n        }\n        return ans;\n    }\n```\ncomplexity would be O(kn^3)\n\noptimization: using memoization, we can reduce the cost(i,j) problem into another dp problem, the complexity would be O(kN^2)\ndp[l,k] is the min cost for length l (starting from beginning) with k parts, dp1[i,j] is the cost to make s[i,j] to be one palindrome part.\ndp1[i,j]=dp[i+1,j-1]+(s[i]!=s[j]).\n\n```cpp\n    int palindromePartition(string s, int k) {\n        //two dp problem: dp1[l,k] cost for string from begin to l with k parts\n        //dp2[i,j] cost for string s[i,j] as one parts\n        int n=s.size();\n        vector<vector<int>> dp(n+1,vector<int>(k+1,n)),dp1(n,vector<int>(n)); //min replace length of string with k parts\n        dp[0][0]=0;\n        for(int i=1;i<=n;i++){ //length \n            for(int j=1;j<=k;j++){ //number of pal groups\n                for(int l=i-1;l>=0;l--) //start \n                {\n                    dp1[l][i-1]=(l+1<i-1?dp1[l+1][i-2]:0)+(s[l]!=s[i-1]);\n                    dp[i][j]=min(dp[l][j-1]+dp1[l][i-1],dp[i][j]);\n                }\n            }\n        }\n        return dp[n][k];\n    }\n```
[]