short python cache based DP solution
\ndef palindromePartition(self, s: str, k: int) -> int:\n        @lru_cache(maxsize=None)\n        def nchange(i, j):\n            res = 0\n            while i 
```\ndef palindromePartition(self, s: str, k: int) -> int:\n        @lru_cache(maxsize=None)\n        def nchange(i, j):\n            res = 0\n            while i < j:\n                if s[i] != s[j]:\n                    res += 1\n                i,j = i+1, j-1\n            return res\n        \n        @lru_cache(maxsize=None)\n        def part(st, k):\n            if k == 1: return nchange(st, len(s)-1)\n            res = math.inf\n            for i in range(st, len(s)):\n                res = min(res, nchange(st, i) + part(i+1, k-1))\n            return res\n        return part(0, k)\n```
[]