d(i, j)表示第i天到第j天至少要穿多少件衣服。
先不考虑第i天和后面 i+1 ~ j 天的联系，那就是至少要穿 1 + d(i+1, j)件衣服。
再看状态转移，如果后面第k(i+1 ≤ k ≤ j)天所穿的衣服和第i天一样的话，那么完全可以把第i+1~k-1天所穿的衣服脱下来。
所以状态转移方程就是d(i, j) = min{ d(i+1, k-1) + d(k, j) | a[i] == a[k] }，这里不用加1，因为第i天穿的那件衣服，已经包含在d(k, j)中了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = + ; int n;
int a[maxn];
int d[maxn][maxn]; int main()
{
int T; scanf("%d", &T);
for(int kase = ; kase <= T; kase++)
{
scanf("%d", &n);
for(int i = ; i < n; i++) scanf("%d", a + i);
memset(d, , sizeof(d));
for(int i = ; i < n; i++)
for(int j = i; j < n; j++)
d[i][j] = j - i + ;
for(int i = n - ; i >= ; i--)
for(int j = i + ; j < n; j++)
{
d[i][j] = d[i + ][j] + ;
for(int k = i + ; k <= j; k++) if(a[i] == a[k])
d[i][j] = min(d[i][j], d[i+][k-] + d[k][j]);
}
printf("Case %d: %d\n", kase, d[][n - ]);
} return ;
}
代码君