LeetCode-1278 分割回文串 III

Table of Contents

LeetCode-1278 分割回文串 III #

Solution 1 #

用 dp[i][j] 代表修改子串 s[i:j+1] 为回文串所需要的最少操作次数. $f(i, t)$ 表示将 $s[i:]$ 分割成 $t$ 个回文串所需要的最少操作次数. 用 $f(i, t) = \min_{j >= i} (dp[i][j] + f(j + 1, t - 1))$ 来转移.

代码如下:

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        dp = [[0 for _ in range(n)] for _ in range(n)]
        for l in range(1, n + 1):
            for i in range(n - l + 1):
                j = i + l - 1
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] if i < n - 1 and j > 0 else 0
                else:
                    dp[i][j] = (dp[i + 1][j - 1] if i < n - 1 and j > 0 else 0) + 1

        ans = 0
        @cache
        def f(i, t):
            if t == 0 and i < n:
                return inf
            if i == n:
                return 0 if t == 0 else inf
            res = inf
            for j in range(i, n - (t - 1)):
                res = min(res, dp[i][j] + f(j + 1, t - 1))
            return res 
        
        return f(0, k)