Java Solution beats 91%
\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        int n = s.length();\n        int[][] dp = new int[n][k+1];\n        int[][] h
```\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        int n = s.length();\n        int[][] dp = new int[n][k+1];\n        int[][] ht = new int[n][n];\n        for (int j = 1; j < n; j++) {\n            for (int i = 0; i < n-j; i++) {\n                if (s.charAt(i) == s.charAt(i+j))\n                    ht[i][i+j] = ht[i+1][i+j-1];\n                else\n                    ht[i][i+j] = ht[i+1][i+j-1]+1;\n            }\n        }\n        for (int i = n-1; i > -1; i--) {\n            dp[i][1] = ht[i][n-1];\n            for (int j = 2; j < Math.min(k+1, n-i+1); j++) {\n                dp[i][j] = n;\n                for (int r = i; r < n-j+1; r++)\n                    dp[i][j] = Math.min(dp[i][j], ht[i][r] + dp[r+1][j-1]);\n            }\n        }\n        return dp[0][k];\n    }\n}\n```
[]