Java dp sol, first get all the substring cost, then do the dp
\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        int costs[][]=new int[s.length()][s.length()];\n        int ans=Integer.MAX_V
```\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        int costs[][]=new int[s.length()][s.length()];\n        int ans=Integer.MAX_VALUE;\n        for(int i=0;i<s.length();i++){\n            for(int j=i+1;j<s.length();j++){\n                costs[i][j]=change(s,i,j);\n            }\n        }\n        if(k==1){\n            return costs[0][s.length()-1];\n        }\n        \n        int dp[][]=new int[k][s.length()]; // row:\u5200  \n        //partition into two\n        \n        \n        //k=1\n        for(int i=1;i<s.length();i++){\n            int val=Integer.MAX_VALUE;\n            for(int j=1;j<=i;j++){\n                val=Math.min(val,costs[0][j-1]+costs[j][i]);\n            }\n            dp[1][i]=val;\n        }\n        \n         for(int row=2;row<dp.length;row++){ //row:k\n            for(int col=row;col<s.length();col++){\n                int val=Integer.MAX_VALUE;\n                for(int j=1;j<=col;j++){\n                    val=Math.min(val,dp[row-1][j-1]+costs[j][col]);\n                }\n                dp[row][col]=val;\n            }\n        }\n        return dp[dp.length-1][dp[0].length-1];\n    }\n    \n    public int change(String s,int left,int right){\n        int cost=0;\n        while(left<right){\n            if(s.charAt(left)!=s.charAt(right)){\n                cost++;\n            }\n            left++;\n            right--;\n        }\n        return cost; \n    }\n}\n```
[]