Java solution, recursive + caching and iterative have explaination
\nIterative Explaination:\n\n1) count how many change to make substring become palindrome, we could apply dynamic programming to count\n2) call dp[i] is minimum
```\nIterative Explaination:\n\n1) count how many change to make substring become palindrome, we could apply dynamic programming to count\n2) call dp[i] is minimum change to make substrings start at i to palindrome - dp[0] is substrings start from 0, this is result we need to find\n3) K split substrings - we need to loop through k times to choose substrings\n\tfor(int kt = 1; kt <= k; kt++) {\n\t\t///\n\t}\n\t\n\tkt = 1; only 1 substring left\n\tkt = 2; 2 substring left\n\t...\n\tkt = k; k substring left\n\tWe need to start from kt = 1, with one substring left what is the minimum change to make these string is palindrome\n4) for(int begin = 1; begin < s.length() - kt + 1; begin++) {\n\t\tfor(int end = begin; end < s.length() - kt + 1; end++) {\n\t\t\t//\n\t\t}\n\t}\n\t\n\tat begin index we have multiple way to split substrings depend on end index start from begin -> end of string but we need to keep track which substring have minimum change to make panlindrome\n\n```\n\n\n```\n\n**Recursive**\n\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        Integer[][] cache = new Integer[s.length()][k + 1];\n        int[][] dp = new int[s.length()][s.length()];\n        \n        for(int i = dp.length - 1; i >= 0; i--) {\n            for(int j = i + 1; j < dp[0].length; j++) {\n                int val = (i + 1 <= j - 1) ? dp[i + 1][j - 1] : 0;  \n                dp[i][j] = s.charAt(i) != s.charAt(j) ? val + 1 : val;\n            }\n        }\n        \n        return helper(s, k, 0, cache, dp);\n    }\n    \n    private int helper(String s, int k, int i, Integer[][] cache, int[][] dp) {\n        if (i == s.length()) {\n            if (k == 0) return 0;\n            return -1;\n        }\n        \n        if (k == 0) return -1;\n        \n        if (cache[i][k] != null) return cache[i][k];\n        \n        StringBuilder sb = new StringBuilder();\n        int min = Integer.MAX_VALUE;\n        for(int j = i; j < s.length(); j++) {\n            sb.append(s.charAt(j));\n            int val = helper(s, k - 1, j + 1, cache, dp);\n            if (val == -1) continue;\n            min = Math.min(min, dp[i][j] + val);\n        }\n        \n        cache[i][k] = min == Integer.MAX_VALUE ? -1 : min;\n        \n        return cache[i][k];\n    }\n}\n```\n\n```\n\n**Iterative**\n\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        \n        int[][] countChange = new int[s.length()][s.length()];\n        for(int i = countChange.length - 1; i >= 0; i--) {\n            for(int j = i + 1; j < countChange[0].length; j++) {\n                int val = (i + 1 <= j - 1) ? countChange[i + 1][j - 1] : 0;\n                countChange[i][j] = (s.charAt(i) == s.charAt(j)) ? val : val + 1;\n            }\n        }\n        \n        int[] dp = new int[s.length()];\n        \n        for(int kt = 1; kt <= k; kt++) {\n            for(int begin = 0; begin < s.length() - kt + 1; begin++) {\n                if (kt == 1) {\n                    dp[begin] = countChange[begin][s.length() - 1];\n                    continue;\n                }\n                \n                dp[begin] = Integer.MAX_VALUE;\n                for(int end = begin; end < s.length() - kt + 1; end++) {\n                    dp[begin] = Math.min(dp[begin], countChange[begin][end] + dp[end + 1]);\n                }\n            }\n        }\n        \n        return dp[0];\n    }\n}\n\n\n```\n\n
[]