Java - DP
\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        if (s == null || s.length() == 0) {\n            return 0;\n        }\n      
```\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        if (s == null || s.length() == 0) {\n            return 0;\n        }\n        int n = s.length();\n        // states\n        int[][] f = new int[n + 1][k + 1];\n        // initialization\n        for (int i = 1; i <= n; i++) {\n            for (int j = 0; j <= k; j++) {\n                f[i][j] = Integer.MAX_VALUE / 2;\n            }\n        }\n        // function\n        for (int i = 1; i <= n; i++) {\n            for (int p = 1; p <= Math.min(i, k); p++) {\n                for (int j = i; j >= p; j--) {\n                    f[i][p] = Math.min(f[i][p], f[j - 1][p - 1] + count(s, j, i));\n                }\n            }\n        }\n        // answer\n        return f[n][k];\n    }\n    \n    public int count(String s, int start, int end) {\n        if (start >= end) {\n            return 0;\n        }\n        int ans = 0;\n        for (int i = start, j = end; i < j; i++, j--) {\n            if (s.charAt(i - 1) != s.charAt(j - 1)) {\n                ans++;\n            }\n        }\n        return ans;\n    }\n}\n```
[]