Java || DP
```\nclass Solution {\n    Boolean[][] Bdp;\n    public boolean isPalindrome(String s, int st, int end) {\n        if (st == end) {\n            return true;\n 
```\nclass Solution {\n    Boolean[][] Bdp;\n    public boolean isPalindrome(String s, int st, int end) {\n        if (st == end) {\n            return true;\n        }\n        if (Bdp[st][end] != null) {\n            return Bdp[st][end];\n        }\n        return (s.charAt(st) == s.charAt(end)) && isPalindrome(s, st + 1, end - 1);\n    }\n    \n    public int palindromePartition(String s, int k) {\n        int n = s.length();\n        if (k == n){\n            return 0;\n        }\n        Bdp = new Boolean[n][n];\n        int[][] dp = new int[n][n];\n        for (int gap = 1; gap < n; gap++) {\n            for (int i = 0, j = gap; j < n; j++, i++) {\n                if (gap == 1) {\n                    if (s.charAt(i) != s.charAt(j)) {\n                        dp[i][j] = 1;\n                    }\n                } else {\n                    if (s.charAt(i) == s.charAt(j)) {\n                        dp[i][j] = dp[i + 1][j - 1];\n                    } else {\n                        dp[i][j] = dp[i + 1][j - 1] + 1;\n                    }\n                }\n            }\n        }\n        Integer[][] finalDP = new Integer[n][k + 1];\n        return getMin(s, 0, k, dp, finalDP);\n    }\n    \n    //  minimum number of changes needed in \'s\' from st to end to partition in k substrings\n    public int getMin(String s, int st, int k, int[][] dp, Integer[][] finalDP) {\n        if (st == s.length() && k > 0) {\n            return 100;\n        }\n        if (finalDP[st][k] != null) {\n            return finalDP[st][k];\n        }\n        if (k == 1) {\n            return dp[st][s.length() - 1];\n        }\n        int ans = Integer.MAX_VALUE;\n        for (int i = st; i < s.length(); i++) {\n            ans = Math.min(ans, dp[st][i] + getMin(s, i + 1, k - 1, dp, finalDP));\n        }\n        finalDP[st][k] = ans;\n        return ans;\n    }\n}
[]