Leetcode 2911. Minimum Changes to Make K Semi-palindromes

• Leetcode 2911. Minimum Changes to Make K Semi-palindromes
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：2911. Minimum Changes to Make K Semi-palindromes

1. 解题思路

这一题属实也是把我坑惨了……

坦率地说，这道题本身并没有啥难度，但是坑爹的是题目表述简直有毒，有两个细节题目里面压根没提，一个是我从中文版本的题目当中发现的，另一个则是我根据失败的样例当中反推出来的，这简直有毒……

这道题本身思路上还是挺直接的，就是一个动态规划的题目，考虑每一种切分的方式，然后考察其中最小的变化次数即可。

然后对于每一个切分得到的子串，我们要求其变化所需的最小变化次数，我们只需要找到其所有对长度$l$整除的$d$，然后切分semi子串，再考察其中每一种分法下所需的变化次数之和，最后取最小值即可。

因此，我们就将上述题目拆分完成了，后续只要对其实现一下即可，测试发现是可以在有效时间内完成所有测试样例的。

但是，这里但是就来了，题目中遗漏了两个非常非常重要的说明，把我给坑惨了！！！

首先，这里semi-palindrome的定义事实上要求将其使用d进行切分后，每一个子串都得是回文，其次，题中也没有具体说，但是实际测试发现，这里对子串的切分要求每一个子串长度至少为2。

这简直就是简直了！！！

到底谁出的题目啊，只能说，出来挨打！！！

2. 代码实现

给出python代码实现如下：

class Solution:def minimumChanges(self, s: str, k: int) -> int:n = len(s)@lru_cache(None)def count(sub):cnt = 0n = len(sub)for i in range(n//2):if sub[i] != sub[n-1-i]:cnt += 1return cnt@lru_cache(None)def count_change(s):if s == s[::-1]:return 0n = len(s)ans = count(s)for d in range(len(s)//2, 0, -1):if n % d != 0:continuek = n // dcnt = 0for i in range(d):sub = "".join([s[i+j*d] for j in range(k)])cnt += count(sub)ans = min(ans, cnt)return ans@lru_cache(None)def dp(idx, k):if idx+2*k > n:return math.infelif k == 1:return count_change(s[idx:])return min(count_change(s[idx:j]) + dp(j, k-1) for j in range(idx+2, n))ans = dp(0, k)return ans   

提交代码评测得到：耗时5650ms，占用内存71.8MB。