Python DP recursive solution with explanation
\nfrom functools import lru_cache as cache\nclass Solution:\n    def palindromePartition(self, s: str, k: int) -> int:\n        \n        \'\'\'\n        Write 
```\nfrom functools import lru_cache as cache\nclass Solution:\n    def palindromePartition(self, s: str, k: int) -> int:\n        \n        \'\'\'\n        Write a function to get min number of letters to change to make a string a palindrome.\n        \n        Recursive function: for each prefix, min_change(prefix) + helper(suffix, count - 1). \n        \n        If count is 1, return min_change(prefix).\n        If count is higher than the length of the prefix, there are no possible solutions, so return inf to discourage this choice. \n        Get min for all options.\n        \n        Use cache to reuse answers.\n        \n        Use indices instead of substrings, to save time spent string slicing and to save space in cache keys.\n        (Substring solution commented out below).\n        \'\'\'\n        \n        @cache(None)\n        def min_change(l, r):\n            count = 0\n            \n            while l < r:\n                if s[l] != s[r]:\n                    count += 1\n                l += 1\n                r -= 1\n            \n            return count\n        \n        @cache(None)\n        def helper(i, j, count):\n            if (j - i + 1) < count:\n                return float(\'inf\')\n            \n            if count == 1:\n                return min_change(i, j)\n            \n            ans = float(\'inf\')\n            \n            for x in range(i, j):\n                tmp = min_change(i, x) + helper(x+1, j, count - 1)\n                ans = min(ans, tmp)\n                \n            return ans\n        \n        return helper(0, len(s)-1, k)\n    \n# This is what the helper function would look like with string slicing.\n# I find this easier to write at first, then change it to use indices. \n        \n#         def helper(prefix, count):\n#             if len(prefix) < count:\n#                 return float(\'inf\')\n            \n#             if count == 1:\n#                 return min_change(prefix)\n            \n#             ans = float(\'inf\')\n            \n#             for i in range(1, len(prefix)+1):\n#                 tmp = min_change(prefix[:i]) + helper(prefix[i:], count - 1)\n#                 ans = min(ans, tmp)\n                \n#             return ans\n        \n#         return helper(s, k)\n```
['Dynamic Programming', 'Recursion', 'Python', 'Python3']