1278. 分割回文串 III

Difficulty
Hard
Tags
动态规划
URL
https://leetcode-cn.com/problems/palindrome-partitioning-iii/
Star
给你一个由小写字母组成的字符串 s，和一个整数 k。
请你按下面的要求分割字符串：
  • 首先，你可以将 s 中的部分字符修改为其他的小写英文字母。
  • 接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。
请返回以这种方式分割字符串所需修改的最少字符数。
示例 1：
输入：s = "abc", k = 2
输出：1
解释：你可以把字符串分割成 "ab" 和 "c"，并修改 "ab" 中的 1 个字符，将它变成回文串。
示例 2：
输入：s = "aabbc", k = 3
输出：0
解释：你可以把字符串分割成 "aa"、"bb" 和 "c"，它们都是回文串。
示例 3：
输入：s = "leetcode", k = 8
输出：0
提示：
  • 1 <= k <= s.length <= 100
  • s 中只含有小写英文字母。
通过次数3,878提交次数6,433

法1 动态规划 区间型

dp[i][k] 表示 s[0:i+1] 分割为 k 份最少需要的修改次数。注意一下规则：
  • k = 0 表示切割份数为 0 ，无意义
  • i = 3 表示有四个字符，那么最多切割 4 份。所以k ≤ i + 1
  • 当 k = 1 时, 表示切割一份，这应该是要初始化的。
综上所述，动态规划其实是要填充以下表格。
notion imagenotion image
具体转移方程如下：
dp[i][k] = min(dp[i][k], dp[j-1][k-1]+cost[j][i])
j为向前查找，找到将s[j:i+1] 分为第k份的最佳分割点，那么前面的s[0:j] 就需要分成k-1份，此时，就对j的位置有了限制，因为j前面必须还要有k-1个字符才能分成k-1份。
notion imagenotion image
最后是代价，即将s[i][j+1]的字符转化为回文串最少需要修改的次数。此为第二类区间型问题，较为简单，如下
notion imagenotion image
题解
class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        K = k
        # cost[i][j] 将s[i:j+1] 修改为回文串最少需要的修改次数
        # 是闭区间， 是包含 i j 的
        cost = [[0] * len(s) for _ in s]
        
        for i in range(len(s)-1, -1, -1):
            for j in range(i+1, len(s), 1):
                if s[i] == s[j]:
                    cost[i][j] = cost[i+1][j-1]
                else:
                    cost[i][j] = cost[i+1][j-1] + 1

        dp = [[float("inf")] * (K+1) for _ in s]
        
        # 初始化，先计算分一份的
        for i in range(0, len(s)):
            dp[i][1] = cost[0][i]


        # dp[i][k] 将 s[0:k] 分为 k 份最少的修改数
        for i in range(0, len(s), 1):
            # 从 2 份开始分,因为第一份已经初始化好了
            for k in range(2, K+1, 1):
                # s[i] 最多可以分 i + 1 份
                if k > i + 1:
                    break
                for j in range(i, -1, -1):
                    # 要保证 j-1 前面至少还有 k - 1 个字符
                    if j -1 + 1 < k - 1:
                        break
                    dp[i][k] = min(dp[i][k], 
                                    dp[j-1][k-1]+cost[j][i])

        return dp[-1][K]