Problem statement

https://leetcode.com/problems/palindrome-partitioning-iii/

Solution

Let us have:

  1. fix(i, j) be number of steps to make substring s[i:j] palindrome.
  2. dp(i, T) is answer for from string s[i:] and for T parts.

Complexity

Time complexity is O(n^2 * k), space is O(n^2).

Code

class Solution:
    def palindromePartition(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)