JAVA | Bottom-Up | DP
\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        if(s.length() == k) return 0;\n        int n = s.length();\n        int dp[][
```\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        if(s.length() == k) return 0;\n        int n = s.length();\n        int dp[][] = new int[n][n];\n        \n        //Counting no.of changes to make a substring palindrome for each substring\n        for(int i = n-1; i>=0; i--){\n            for(int j = i; j<n; j++){\n                if(i-j == 0) dp[i][j] = 0;\n                else{\n                    dp[i][j] = dp[i+1][j-1];\n                    if(s.charAt(i) != s.charAt(j)){\n                        dp[i][j] += 1;\n                    }\n                }\n            }\n        }\n       \n        int countdp[][] = new int [k+1][n];\n        \n        // Count min no. of changes for each substring for k partitions\n        for(int i = 1; i<=k; i++){\n            for(int j = 0; j<n; j++){\n                if(i == 1) countdp[i][j] = dp[i-1][j];\n                else{\n                    if(i - j < 1){\n                        int min = 100000;\n                        for(int l = j; l>=i-1 ; l--){\n                            min = Math.min(countdp[i-1][l-1] + dp[l][j], min);\n                            if(min == 0) break;\n                        }\n                        countdp[i][j] = min;\n                    }\n                }\n            }\n        }\n        return countdp[k][n-1];\n    }\n}\n```
['Dynamic Programming', 'Java']