半回文数【Python】

用Python完成：

给你一个字符串 s 和一个整数 k ，请你将 s 分成 k 个 子字符串 ，使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。
请你返回一个整数，表示需要修改的 最少 字符数目。

注意：
如果一个字符串从左往右和从右往左读是一样的，那么它是一个 回文串 。
如果长度为 len 的字符串存在一个满足 1 <= d < len 的正整数 d ，len % d == 0 成立且所有对 d 做除法余数相同的下标对应的字符连起来得到的字符串都是 回文串 ，那么我们说这个字符串是 半回文串 。比方说 "aa" ，"aba" ，"adbgad" 和 "abab" 都是 半回文串 ，而 "a" ，"ab" 和 "abca" 不是。
子字符串 指的是一个字符串中一段连续的字符序列。
 

参考代码如下：

def min_changes(s: str, k: int) -> int: 
    n = len(s) # 找到所有对称的位置 
    sym_pos = [] 
    for i in range(n // 2): 
        if s[i] != s[n - i - 1]: 
            sym_pos.append((i, n - i - 1))
 
# 计算每个子串需要修改的字符数目
def count_changes(left: int, right: int) -> int:
    res = 0
    while left < right:
        if s[left] != s[right]:
            res += 1
        left += 1
        right -= 1
    return res
 
# 动态规划计算从某个位置开始长度为k的子串需要修改的字符数目
dp = [[0] * k for _ in range(n)]
for i in range(n):
    for j in range(i + 1, min(n, i + k) + 1):
        dp[i][j % k] = dp[i][j % k - 1] + count_changes(i, j - 1)
 
# 选择k个子串，使得修改量最少
memo = {}
def dfs(pos: int, remain_k: int) -> int:
    if remain_k == 1:
        return dp[pos][0]
    if (pos, remain_k) in memo:
        return memo[(pos, remain_k)]
    res = float('inf')
    for i in range(pos + 1, n):
        if i - pos >= k:
            break
        res = min(res, dfs(i, remain_k - 1) + dp[pos][i % k])
    memo[(pos, remain_k)] = res
    return res
 
return dfs(0, k)

具体实现如下：

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        # dp[i][j]表示将s[i:j]变成回文串所需最少修改次数
        dp = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1]
                else:
                    dp[i][j] = dp[i + 1][j - 1] + 1
        # memo[(i,k)]表示将s[i:]分成k个半回文串所需最少修改次数
        memo = {}
        def dfs(i: int, k: int) -> int:
            if (i, k) in memo:
                return memo[(i, k)]
            if n - i == k:
                return 0
            if k == 1:
                return dp[i][n - 1]
            res = float('inf')
            for j in range(i, n - k + 1):
                res = min(res, dp[i][j] + dfs(j + 1, k - 1))
            memo[(i, k)] = res
            return res
        return dfs(0, k)

思路解析： 首先，根据题目定义，对于一个半回文串，我们只需要将它的中心线两侧的字符变成相同即可。因此，我们可以使用动态规划来计算将一个子串变成回文串所需最少的修改次数，具体地，令$dp_{i,j}$表示将$s_{i:j}$变成回文串所需最少修改次数，则有：

$$ dp_{i,j}=\left{ \begin{aligned} &dp_{i+1,j-1}&\ \text{if}\ s_i=s_j\ &dp_{i+1,j-1}+1&\ \text{otherwise} \end{aligned} \right. $$

接下来，考虑如何将字符串$s$分成$k$个半回文串，使得修改次数最少。我们可以使用记忆化搜索，令$memo_{i,k}$表示将$s_{i:}$分成$k$个半回文串所需最少修改次数。具体地，对于当前位置$i$和还需要分割的份数$k$，我们枚举当前半回文串的右端点$j$，并计算将$s_{i:j}$变成回文串所需的修改次数$dp_{i,j}$，然后递归处理剩余部分即可。最终答案即为$memo_{0,k}$。

示例

s = "abcdeca" k = 2 print(min_changes(s, k)) # 输出2