难度: Hard
Submission
运行时间: 264 ms
内存: 16.8 MB
class Solution:
def minimumMoves(self, arr: List[int]) -> int:
n=len(arr)
f=[[n]*n for _ in range(n)]
g=[None]*n
for i,x in enumerate(arr):
f[i][i]=1
g[i]=[j for j in range(i,n) if arr[j]==x]
for i in range(n-2,-1,-1):
for j in range(i+1,n):
if i==j-1:
f[i][j]=int(arr[i]!=arr[j])+1
else:
if arr[i]==arr[j]:
f[i][j]=f[i+1][j-1]
for k in g[i]:
if k>=j:
break
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j])
return f[0][n-1]
Explain
该题解使用动态规划的方法来解决删除回文子数组的问题。使用一个二维数组 f[i][j] 表示将数组 arr[i] 到 arr[j] 变为回文子数组所需的最小操作次数。初始化时，f[i][i] 设为 1 因为单个元素自身就是回文。数组 g 用来存储从每个位置 i 开始，与 arr[i] 相同元素的位置，以优化搜索过程。对于每对 i 和 j，如果 arr[i] 等于 arr[j]，则 f[i][j] 可直接设为 f[i+1][j-1]。否则，通过遍历 g[i] 中存储的位置，将问题分解为更小的子问题，即将原问题 f[i][j] 分解为 f[i][k] + f[k+1][j] 的形式来计算，其中 k 是 g[i] 中的元素，但需小于 j。
时间复杂度: O(n^3)
空间复杂度: O(n^2)
class Solution:
def minimumMoves(self, arr: List[int]) -> int:
n = len(arr)
f = [[n] * n for _ in range(n)] # 初始化动态规划数组 f
g = [None] * n # 初始化位置列表数组 g
for i, x in enumerate(arr):
f[i][i] = 1 # 单个元素是回文
g[i] = [j for j in range(i, n) if arr[j] == x] # 存储与 arr[i] 相同的元素的位置
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
if i == j - 1:
f[i][j] = int(arr[i] != arr[j]) + 1 # 相邻元素处理
else:
if arr[i] == arr[j]:
f[i][j] = f[i + 1][j - 1] # 如果首尾相等，则内部问题解决
for k in g[i]:
if k >= j:
break
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]) # 分解为子问题求解
return f[0][n - 1] # 返回整个数组的最小删除次数
Explore
在这个算法中，`f[i][j]`表示将子数组`arr[i]`到`arr[j]`变为回文子数组所需的最小操作次数。初始化`f[i][j]`为`n`（数组的长度）是因为在最坏的情况下，把每一个元素单独变成一个回文子数组（即删除所有其他元素）可能需要`n-1`次操作，因此将所有元素的初始值设为`n`是一种安全的上界设定。这样的初始化保证了动态规划过程中的每一步都是从可能的最大操作次数开始逐渐寻找更小的数值，从而确保找到真正的最小操作次数。
数组`g[i]`存储了所有与`arr[i]`相同值的元素位置，这样做可以直接跳过那些值不同的元素，直接关注那些可能与`arr[i]`构成更长回文序列的元素。在动态规划的每一步，特别是在处理`arr[i]`与`arr[j]`不相等的情况时，这种预存储的信息避免了对每个可能的`k`值都进行测试，从而节省了重复检查每个元素是否与`arr[i]`相同的开销。这种优化减少了不必要的比对和分割尝试，因此可以显著减少算法的时间复杂度。
直接进行简单分割（如总是将`arr[i]`到`arr[j]`分割为`arr[i]`到`arr[k]`和`arr[k+1]`到`arr[j]`）可能不会产生最优解，因为这种简单分割没有考虑到元素值的匹配和回文的可能性。通过遍历`g[i]`来查找所有可能的分割方法，算法可以将`arr[i]`与同值的`arr[k]`进行匹配，这样的分割更有可能形成较大的回文子数组，从而减少总的操作次数。此外，这种方法利用了已经确定能形成回文的元素对，从而避免了无效的分割尝试，确保了算法的效率和结果的最优性。