// 这一份代码通过了
#include <cstdio>
#include <cstring>
#include <memory.h>
#include <algorithm>
using namespace std;
const int maxn = 1000 + 5;
bool is[maxn][maxn];
int dp[maxn], n;
char str[maxn];
int main()
{
//	freopen("in.txt", "r", stdin);
	int t;	scanf("%d", &t);	str[0] = '*';
	while (t--)
	{
		scanf("%s", str + 1);	n = strlen(str + 1);
		memset(dp, 0x3f, sizeof dp);	dp[0] = 0;
//		↓这一行
		memset(is, 0, sizeof is);
		for (int i = 1;i <= n;i++)
			is[i][i] = true;
//		mark2↓
//		int l, r
//		for (int i = 1;i <= n;i++)
//			for (int k = 1;k < i;k++)
//			{
//				if ((i - k) % 2)
//					l = (i + k) / 2, r = l + 1;
//				else
//					l = (i + k) / 2 - 1, r = l + 2;
//				is[k][i] = true;
//				while (l >= k)
//				{
//					if (str[l] != str[r])
//					{
//						is[k][i] = false;
//						break;
//					}
//					l--, r++;
//				}
//			}
		for (int i = 1;i <= n;i++)
		{
			if (str[i - 1] == str[i])
				is[i - 1][i] = true;
			for (int k = i - 2;k > 0;k--)
				is[k][i] = (is[k + 1][i - 1] && str[k] == str[i]);
		}

		for (int i = 1;i <= n;i++)
			for (int k = 0;k < i;k++)
				if (is[k + 1][i])			// 至少 k == i - 1 的时候会更新一次 
					dp[i] = min(dp[i], dp[k] + 1);
		printf("%d\n", dp[n]);
	}
	return 0;
}

AC的记录
WA的记录

WA的原因是注释掉了代码中标注的 memset 那一行
但是我在使用每个 is[k + 1][i - 1] 之前都已经更新完他的值了啊, 并且在后面使用的 is[k + 1][i] 下标都是在给定的数据范围内, 那么为什么有必要 memset 一遍呢
但事实是不这样就 WA