[Python3] DP top-down & bottom-up
Math:\nDefine dp[i][j] as the minimal number of characters that one needs to change to divide the substring s[i:] when it can be divided into j non-empty disjoi
Math:\nDefine `dp[i][j]` as the minimal number of characters that one needs to change to divide the substring `s[i:]` when it can be divided into `j` non-empty disjoint substrings. The recursion eqution is \n`dp[i][j] = min(cost[i,l] + dp[l+1][j-1] for l in range(i, len(s)-j+1)` \nwhere `dp[i][1] = cost[i, len(s)-1]` and `dp[i][len(s)-i] = 0`. \n\nImplemenation 1: top-down implementation with memoization \n```\nfrom functools import lru_cache\n\nclass Solution:\n    def palindromePartition(self, s: str, k: int) -> int:\n        \n        @lru_cache(None)\n        def cost(i, j=len(s)-1): \n            """Return cost of converting string[i:j+1] to palindrome"""\n            return 0 if i >= j else cost(i+1, j-1) + (s[i]!=s[j])\n        \n        @lru_cache(None)\n        def dp(i, j): \n            """Return minimal char change for string[i:] dividing into j substring\n            dp(i, j) = min(cost(i, l) + dp(l+1, j) for l in range(i, len(s)-j))\n            dp(i, 0) = cost(i)\n            dp(i, len(s)-i) = 0 \n            """\n            if j == 1: return cost(i)\n            return min((cost(i, l)+dp(l+1, j-1) for l in range(i, len(s)-j+1)), default=0)\n        \n        return dp(0, k)\n```\n\nImplementation 2: bottom-up\n```\nfrom functools import lru_cache\n\nclass Solution:\n    def palindromePartition(self, s: str, k: int) -> int:\n        \n        @lru_cache(None)\n        def cost(i, j=len(s)-1):\n            return 0 if i >= j else cost(i+1,j-1) + (s[i] != s[j])\n        \n        ans = [cost(i) for i in range(len(s))]\n        for j in range(k-1):\n            for i in range(len(s)-j-1):\n                ans[i] = min((ans[l+1] + cost(i, l) for l in range(i, len(s)-j-1)), default=0)\n                \n        return ans[0]\n```
['Dynamic Programming', 'Python3']