PreProcess + DP
\nclass Solution {\n    public int palindromePartition(String s, int k) {\n\n        // dp[i][j]: means the min changes to cut the string into k parts which end
```\nclass Solution {\n    public int palindromePartition(String s, int k) {\n\n        // dp[i][j]: means the min changes to cut the string into k parts which ends with index i.\n        int dp[][] = new int[s.length()+1][k+1];\n\n        int memo[][] = preprocess(s);\n\n        for (int i=1; i<=s.length(); i++) {\n            dp[i][1] = memo[1][i];\n        }\n\n        for (int i=2; i<=k; i++) {\n            for (int j=2; j<=s.length(); j++) {\n                dp[j][i] = 1000000;\n                for (int p=i-1; p<j; p++) {\n                    int res = dp[p][i-1] + memo[p+1][j];\n                    dp[j][i] = Math.min(dp[j][i], res);\n                }\n            }\n        }\n\n        return dp[s.length()][k];\n    }\n\n    // Calculate how many move to make subString(i, j) as palindrome.\n    public int[][] preprocess(String str) {\n        int N = str.length();\n        int [][] res=  new int [N+1][N+1];\n        char arr[] = str.toCharArray();\n\n\n        for (int l=1; l<=N; l++) {\n            for (int s=1; s+l-1<=N; s++) {\n                int e = s+l-1;\n                if (l == 1) {\n                    res[s][e] = 0;\n                } else {\n                    if (arr[s-1] == arr[e-1]) {\n                        res[s][e] = res[s+1][e-1];\n                    } else {\n                        res[s][e] = res[s+1][e-1] + 1;\n                    }\n                }\n            }\n        }\n\n        return res;\n    }\n}\n```
[]