[Python] easy DP with pre-processing
\nTime complexity : O(n^2*k)\npython\nclass Solution:\n    def palindromePartition(self, s: str, k: int) -> int:        \n        n = len(s)\n        # cost[i][
\nTime complexity : O(n^2*k)\n```python\nclass Solution:\n    def palindromePartition(self, s: str, k: int) -> int:        \n        n = len(s)\n        # cost[i][j]: number of changes to make s[i:j+1] into palindrome string\n        cost = [[0]*n for _ in range(n)]\n        for i in range(n-1, -1, -1):\n            for j in range(i, n):\n                if s[i] != s[j]:\n                    if j-i < 2:\n                        cost[i][j] = 1\n                    else:\n                        cost[i][j] = cost[i+1][j-1] + 1\n                else:\n                    if j-i < 2:\n                        cost[i][j] = 0\n                    else:\n                        cost[i][j] = cost[i+1][j-1]\n\n\n        # dp(i, k) is min changes to make s[:i+1] into k non-empty disjoint substrings and each of them is palindrome.\n        def dp(i, k):\n            if (i, k) in memo:\n                return memo[(i, k)]\n            \n            if k == 1:\n                # k == 1 is unique\n                memo[(i, k)] = cost[0][i]\n            else:\n                # dp[i, k] = min(dp(j, k-1) + cost[j+1][i] for j in range(k-2, i)) where j+1>=k-1\n                memo[(i, k)] = min(dp(j, k-1) + cost[j+1][i] for j in range(k-2, i))\n\n            return memo[(i, k)]\n        \n        memo = {}\n        return dp(n-1, k)\n```
['Dynamic Programming', 'Memoization', 'Python']