2 python3 solutions : recursion + memorization & dp O(k*n^2)
\ndp solution:\nat step k\ncur[j]: the number of changes we need to make considering s[:j] (j inclusive)\nwe need to iterate through all possible combinations o
\ndp solution:\nat step k\ncur[j]: the number of changes we need to make considering s[:j] (j inclusive)\nwe need to iterate through all possible combinations of last group, from only 1 character, 2 characters, ... untill we cannot get more characters from previous groups(i.e, there is only k-1 characters left for k-1 groups).\n\nHere, I used an additional memo to speed up the calculation of the changes requered to make last group a palindrome.\n```\ndef palindromePartition(self, s: str, k: int) -> int:\n\tmemo = collections.defaultdict(int)\n\tfor i in range(len(s)):\n\t\tfor j in range(i, -1, -1):\n\t\t\tmemo[j, i] = memo[j+1, i-1] + (s[i] != s[j])\n\tprev = [memo[0, i] for i in range(len(s))]\n\tfor i in range(2, k+1):\n\t\tcur = [0] * len(s)\n\t\tfor j in range(i, len(s)):\n\t\t\tcur[j] = min(prev[l-1]+memo[l, j] for l in range(j, i-2, -1))\n\t\tprev = cur\n\treturn prev[-1]\n```\n\nrecursion:\n```\nimport functools\n@functools.lru_cache(None)\ndef palindromePartition(self, s: str, k: int) -> int:\n\tif k >= len(s):\n\t\treturn 0\n\tif k == 1:\n\t\treturn sum(s[i] != s[~i] for i in range(len(s)//2))\n\tres = len(s)\n\tfor i in range(1, len(s)):\n\t\tif k-1 > len(s) - i:\n\t\t\treturn res\n\t\tres = min(res, self.palindromePartition(s[:i], 1)+ self.palindromePartition(s[i:], k-1))\n\treturn res\n```\n
['Python']