LeetCode Palindrome Partitioning
0131. Palindrome Partitioning
Medium但是Hard
解①DFS 搜索
官方建议的通解，直接从前缀开始搜索，遇到一个回文串，就把它加入答案中，然后从跳过这个回文串递归，直到串结束。
Tips：
- 在实现上，可以使用一个暂存的向量保存回文子串，在每一步的递归过程中， 把子串加入，等到递归分支结束的时候把这个向量的复制品加入到答案中，然后在每一步递归返回后，弹出这一步加入到暂存向量里的子串，这样这个暂存向量就可以重复利用；
- 这样需要记忆下每个子串 $s[i, j]$ 是否为回文串来避免重复判断
过程略（因为我也没写：）
解②常规DP
AKA 渐进式解决或者说时优方案
按照一般 DP 解决的思路，从子串到全串，每扩展一个字符，就考虑所有以该字符为后缀的子串是否为回文串，如果是，就把这个回文串加到所有回文串串头的子问题的解，并把这些解加进新子串的解中。
相对于解①，常规DP的思路省却了每次从头开始搜索的成本，但代价是需要保存所有子问题的解，这让空间复杂度从 $O(n^2)$ 提高到了 $O(n^3)$ 。
def solve(s: str) -> List[List[str]]:
cache = [[[]]]
n = len(s)
for i in range(1, n+1):
ans = []
for j in range(i):
if s[j:i] == s[j:i][::-1]:
for case in cache[j]:
l = case.copy()
l.append(s[j:i])
ans.append(l)
cache.append(ans)
return cache[n]
运行时间：507 ms (beats 99.22%, ~100%)，内存占用：36.4 MB (beats 7.38%)。
0132. Palindrome Partitioning II
Hard但是Medium
和上题一样的背景，只不过只需要求一个回文子串的最小分割数，但另一方面串的长度从 $16$ 变为 $2000$ ，这使得优化回文串本身判断的过程变得重要了起来。
解①常规DP
如第一题一样地解答，只是稍作修改。
from math import inf
def solve(s: str) -> int:
cache = [0]
n = len(s)
for i in range(1, n+1):
ans = inf
for j in range(i):
if s[j:i] == s[j:i][::-1]:
if ans > cache[j]:
ans = cache[j]
cache.append(ans+1)
return cache[n]-1
运行时间：2794 ms (beats 35.22%)，内存占用： 16.37 MB (beats 89.42%)。
这个运行时间肉眼看起来就不令人满意，接下来将再次通过 DP 来最大优化对于回文子串的判断。
解②组合DP
对于检查子串 $s[j…i]$ 是否是回文串，可以利用前一次检查的结果，也就是 $s[j+1…i-1]$ 是否是回文串，这样只需要判断 $s[j]$ 和 $s[i]$ 的相等性就可以完成回文的判断。
并且这样我们还可以像一般地 DP 里面压缩 $\text{dp}$ 数组那样，只使用一个一维的数组就可以保存回文子串判断的结果。
def solve(s: str) -> int:
n = len(s)
cache = [0] * (n+1)
p = [True] * n
for i in range(n):
ans = inf
for j in range(i+1):
if s[j] == s[i] and (i-j < 2 or p[j+1]):
p[j] = True
if cache[j-1] < ans:
ans = cache[j-1]
else:
p[j] = False
cache[i] = ans + 1
return cache[n-1] - 1
上面实现我们用 $p[j]$ 表示 $s[j..i]$ 是否是回文串。另外还使用了一个不太正规的 Python 技巧（也是容易出隐藏Bug的地方），那就是是 $p[-1]$ 指向尾部的元素，而在初始化的时候，额外申请了一个空间，初始值 $0$ ，而不管这些，好像我们就有了顺序的 $p[-1],p[0],p[1] \dots$ 。
运行时间：548 ms (beats 97.84%)，内存占用：16.28 MB (beats 95.08%) 。
如果加上对特殊情况的优化：
if s == s[::-1]:
return 0
for i in range(1, n):
if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
return 1
那么运行时间可以直接到 161 ms 。
1278. Palindrome Partitioning III
Hard
破题
构成回文的最少修改数这个概念没有遇到过，这会阻碍思路地顺畅运行，不过还是按照一般地 DP 思路，从子串上的递归子问题开始考虑，总可以逐渐理清思路。
如果先从递归的思路入手，可能会更快地搞清楚这个问题，但做题的时候因为连斩了两道系列题，于是想要一步到位，直接提出最优的迭代版本，结果发现有些勉强，整体思路和冗繁的代码细节叠加在一起，直接卡了很久
首先我们发现：
(1). 一个串的回文修改次数可以通过它同一对称轴的子串1的回文修改次数加上两头字符的比较结果2得到
这样我们可以在 $O(n^2)$ 的时间复杂度内计算出所有串的（最小）回文修改次数，这个复杂度怎么说呢，没那么好但也暂且可以接受，总还是允许我们姑且沿着这个思路继续做下去，既然任一子串的回文修改次数是已知的，那么如何由子问题到全局问题呢？
这时看下题目的数据规模：1 <= k <= s.length <= 100 ，非常小，这几乎不是暗示而是明示了题解期望一个主过程是 $O(n^3)$ 的解决方案，这样的话不需要什么，直接通过暴力搜索就可以完成子问题到全局问题的解决：
(2). 从 $k$ 的每个值开始，从子串的每个字符开始（作为分片的位置），检查每一个选择是否可以使这个子串的相应 $k$ 划分的回文修改次数更小，假设子串是 $s_i = s[0..i]$ ，而在子串里切片的位置是 $c$ ，当前检查的 $k$ 值是 $j$ ，预计算的回文修改次数是 $p$，那么我们需要判断得是 $\text{dp}[i][j] = \min(\text{dp}[c-1][j-1] + p[c][i])$ ，这里面还有个限制，就是 $j$ 个分片至少需要长度为 $j$ 的串的长度，$c$ 的选取要满足这个限制。
解①BFS
整体的思路前面已经讲过了，但是本题最花费精力的（对我来说）是迭代版本的编码细节。
计算回文修改次数
存储回文修改次数的数组不妨令为 $p$ ，可令 $p[i][j]$ 存储子串 $s[i..j]$ 的回文修改次。
根据对称轴计算一族同轴子串的回文修改次数，具体计算方式可以是，从轴心到两端，使用两个变量，也就是双指针的方式不断检查是否越界，但如果把越界检查转换为预先确定的区间通常会更好一点3，但这引入了更多的技术细节，首先需要区分偶数轴和奇数轴：
对于偶数轴，需要从 $s[i.. i+1]$ 开始，也就是说，偶数轴的最小单位是一左一右两个单位长度的串，不妨称之为最小串，那么计算半径 $r$ 应该从最小串的左边一个字符 $s[i-1]$ ，和右边一个字符 $s[i+2]$ 开始，左边的最大长度为 $i-1+1=i$ ，右边的最大长度为 $n-1-(i+2)+1=n-i-2$ ，于是有：
for r in 1..=min(i, n-i-2)
对于奇数轴，需要从 $s[i..i]$ 开始，则计算半径 $r$ 从最小串的左边一个字符 $s[i-1]$ ，和右边一个字符 $s[i+1]$ 开始，左边的最大长度为 $i-1+1=i$ ，右边的最大长度为 $n-1-(i+1)+1=n-i-1$ ，于是有：
for r in 1..=min(i, n-i-1)
只需要初始化 $s[i.. i+1]$ 和 $s[i..i]$ 两个子串的回文修改数情况。
改进的方法
按照原来的存储方法，$p$ 有一半的空间是闲置浪费的，因为我们实际上只存储 $p[i][j], (i\leqslant j)$ 而不存储 $p[j][i]$ ，可以找到一个更适合的办法，其中一个比较好的是 $i$ 指示串的起始位置，而 $j$ 指示串的长度，这样对于二维数组可以根据 $i$ 来精准分配第二维数组的长度。
这里给与第二维的数组开头额外一个长度，避免额外的初始化，这样 $p[i][j]$ 代表长度 $j$ 的子串
对于计算方法，也可以使用长度作为一个维度的变量， 这样避免过多考虑区间的细节。
from math import inf
def solve(s: str, k: int) -> int:
n = len(s)
p = [[0] * (n-i+1) for i in range(n)]
# for i in range(n-1):
# p[i][1] = 0 if s[i] == s[i+1] else 1
# # even
# for r in range(1, min(i-1+1, n-1-(i+2)+1)+1):
# p[i-r][2*r+1] = p[i-r+1][2*r+1-2] + (0 if s[i-r] == s[i+1+r] else 1)
# # odd
# for r in range(1, min(i-1+1, n-1-(i+1)+1)+1):
# p[i-r][2*r] = p[i-r+1][2*r-2] + (0 if s[i-r] == s[i+r] else 1)
for span in range(2, n+1):
for i in range(n-span+1):
p[i][span] = p[i+1][span-2] + (0 if s[i] == s[i+span-1] else 1)
dp = [[0] * k for _ in range(n)]
for i in range(1, n):
dp[i][0] = p[0][i+1]
for j in range(1, min(i+1, k)):
dp[i][j] = inf
for c in range(j, i+1):
if dp[i][j] > dp[c-1][j-1] + p[c][i-c+1]:
dp[i][j] = dp[c-1][j-1] + p[c][i-c+1]
return dp[n-1][k-1]
运行时间：120 ms (beats 73.20%), 内存占用：16.34 MB (beats 94.33%, ~100%) 。
解②DFS
前面迭代版本的实现，可以被认为是对解空间做 BFS ，而递归实现的版本可以认为是 DFS 的一种解法。
直接把预处理和解的搜索都变为递归实现。
from functools import cache
def solve(s: str, k: int) -> int:
n = len(s)
@cache
def recur(i, j) -> int:
if j == 1:
return p(i, n-1)
elif j == n-i:
return 0
else:
return min(p(i, c) + recur(c+1, j-1) for c in range(i, n-(j-1)))
@cache
def p(i, j) -> int:
if j-i == 0:
return 0
elif j-i == 1:
return (0 if s[i] == s[j] else 1)
else:
return (0 if s[i] == s[j] else 1) + p(i+1, j-1)
return recur(0, k)
运行时间：71 ms (beats 94.85%, ~100%)，内存占用： 17.26 MB (beats 51.03%) 。
1745. Palindrome Partitioning IV
破题
完全类似于 1278. Palindrome Partitioning III
解①BFS
def solve(s: str) -> bool:
n = len(s)
p = [[True] * (n-i+1) for i in range(n)]
for span in range(2, n+1):
for i in range(n-span+1):
p[i][span] = p[i+1][span-2] and s[i] == s[i+span-1]
for i in range(n-2):
if p[0][i+1]:
for j in range(i+1, n-1):
if p[i+1][j-i] and p[j+1][n-1-j]:
return True
return False
运行时间：1892 ms (beats 87.50%), 内存占用：16.48 MB (beats 54.17%) 。
解②常规
这道题更快并且更省内存的解法是预先计算所有前缀和后缀的回文子串（暴力比较），然后在这些回文子串选项中寻找解，同样暴力比较。
注解
