BinarySearch 0764 Split String Into K Palindromes

Problem statement

https://binarysearch.com/problems/Split-String-Into-K-Palindromes/

Solution

Equal to Leetcode 1278. Palindrome Partitioning III.

Complexity

It is O(n^2k) for time and O(n^2) for space.

Code

class Solution:
    def solve(self, s, k):
        n = len(s)
        
        @lru_cache(None)
        def fix(i, j):
            if j - i < 1: return 0
            return fix(i + 1, j - 1) + (s[i] != s[j])
        
        @lru_cache(None)
        def dp(i, T):
            if i == n: return abs(T)*n
            return min(fix(i, k) + dp(k+1, T-1) for k in range(i, n))
        
        return dp(0, k)