Similar to MCN | Java solution | Recurrence relation | detailed explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n     recurrence relation :\n     \n     f(s, cuts, i) = 0 , if i >= s.length()\n     f(
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n     recurrence relation :\n     \n     f(s, cuts, i) = 0 , if i >= s.length()\n     f(s, cuts, i) = changeRequired(s, i, s.length()-1), if cuts = 0\n     \n     otherwise:\n     f(s, cuts, i) = min{changeRequired(s, i, k) + f(s, cuts-1, k+1)}, where i <= k < s.length() -1, as for length p, there will be p-1 max cut\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        int [][] dp = new int [s.length()][k+1];\n        for(int [] a : dp) Arrays.fill(a, -1);\n        return solve(s, k, 0, dp);\n    }\n\n    private int solve(String s, int cuts, int i, int [][] dp){\n        if(i >= s.length()) return 0;\n\n        if(dp[i][cuts] != -1) return dp[i][cuts];\n        if(cuts == 1){\n            return changeRequired(s, i, s.length()-1);\n        }\n\n        long minCost = Integer.MAX_VALUE;\n\n        for(int k = i; k < s.length() -1; k++){\n            long ans = (long)changeRequired(s, i, k) + solve(s, cuts-1, k+1, dp);\n            minCost = Math.min(minCost, ans);\n        }\n\n        return dp[i][cuts] = (int)minCost;\n    }\n\n    private int changeRequired(String s, int i, int j){\n        int count = 0;\n        while(i < j){\n            if(s.charAt(i) != s.charAt(j)) count ++;\n            i++;\n            j--;\n        }\n        return count;\n    }\n}\n```
['Java']