一行个数组成序列
，你可以每次取走一个连续的回文子段，取完之后，这些数字又会连缀在一起。现在问你将这些数字全部消除，所需要的最小操作次数。
例如输入：
5
1 4 3 1 5
10
1 3 2 4 5 1 2 3 4 4
输出为
3
5
因为第一个样例中：第一次，你可以取走3，第二次，你可以取走1 4 1，第三次你可以取走5。容易发现次数不会比3次更小了。
今天带来一道难度稍大的问题，用作区间动态规划的例题。直接思考的话，似乎没有什么规律可言。想到动态规划，无论什么状态也似乎互相影响，得不到转移方程。
这里给一个比较套路化的解法：
首先我们定义状态为区间
这个子段，进行消除的最小次数。那么要求的答案就是
转移的方式需要推理。这里我们关注第一个元素会如何进行消除。倘若
被单独消除，那么总次数就是
。否则，
存在于区间
的一个非连续回文串中，假设和
匹配的是
。那么我们注意到，在
被消除之前，
是一直存在的，我们没有办法跨过
来删除一个回文串，而
消失时区间
必然已经消失。因此，区间
的消除与区间
的消除，实质上是完全独立不影响的（仔细体会这一点）。
而对于区间，
和中间的回文串可以形成新回文串，当然也可能
，中间无字符。所以贡献为
。因此，第二种情况的总次数为：
最后注意更新的顺序，必须要从窄区间更新到宽区间，所以首先枚举窄区间。
n = int(input())
s = [0] + list(map(int, input().split()))
dp = [[0] * (n + 2) for i in range(n + 2)]
for l in range(1, n + 1):
for i in range(1, n - l + 2):
j = i + l - 1
if l == 1:
dp[i][j] = 1
else:
dp[i][j] = dp[i + 1][j] + 1
for k in range(i + 1, j + 1):
if s[i] == s[k]:
dp[i][j] = min(dp[i][j], max(dp[i + 1][k - 1], 1) + dp[k + 1][j])
print(dp[1][n])
复杂度
最后这里放一题相似的题目：
https://codeforces.com/contest/1132/problem/F
用类似本题的想法也可以求解
