Python3 Top-down DFS with Memoization
\nclass Solution:\n    def palindromePartition(self, s: str, k: int) -> int:\n        n = len(s)\n        memo = {}\n        \n        def cost(s,i,j): #calcula
```\nclass Solution:\n    def palindromePartition(self, s: str, k: int) -> int:\n        n = len(s)\n        memo = {}\n        \n        def cost(s,i,j): #calculate the cost of transferring one substring into palindrome string\n            r = 0\n            while i < j:\n                if s[i] != s[j]:\n                    r += 1\n                i += 1\n                j -= 1\n            return r\n        \n        def dfs(i, k):\n            if (i, k) in memo: return memo[(i, k)] #case already in memo\n            if n - i == k: #base case that each substring just have one character\n                return 0\n            if k == 1:    #base case that need to transfer whole substring into palidrome\n                return cost(s, i, n - 1)\n            res = float(\'inf\')\n            for j in range(i + 1, n - k + 2): # keep making next part of substring into palidrome\n                res = min(res, dfs(j, k - 1) + cost(s,i, j - 1)) #compare different divisions to get the minimum cost\n            memo[(i, k)] = res\n            return res\n        return dfs(0 , k)\n# I really appreciate it if u vote up! \uFF08\uFFE3\uFE36\uFFE3\uFF09\u2197\n```
[]