Java O(N^2*k) DP solution, similar to 813. Largest Sum of Averages
\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        int len = s.length();\n        int [][] dp = new int [len][k+1];\n        int
```\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        int len = s.length();\n        int [][] dp = new int [len][k+1];\n        int [][] count = new int [len][len];\n        for(int i=0;i<len;i++){\n            for(int j = 0;j<=i;j++){\n                count[j][i]= getPalindrome(s,j,i);\n            }\n            dp[i][1]=count[0][i];\n        }\n   \n        \n        for(int dis = 2; dis<=k;dis++){\n           for(int end = dis-1; end<len;end++){\n               if(dis==k&&end<len-1) continue;\n               dp[end][dis]= end/2+1;\n               for(int start=dis-2;start<end;start++){\n                   dp[end][dis]= Math.min(dp[end][dis],dp[start][dis-1]+count[start+1][end]);\n               }\n           }\n        }\n        return dp[len-1][k];\n    }\n    \n    private int getPalindrome(String s, int start, int end){\n         int num = 0;\n         while(start<=end){\n             if(s.charAt(start++)!=s.charAt(end--)){\n                 num++;\n             }\n         } \n        return num;\n    }\n}\n\n```
[]