题意：有n天，每天有每天要穿的衣服，你可以购买当天要穿的衣服套在原有的衣服上，如果你有这件衣服，你可以把上面的衣服全部丢掉，直到你需要的衣服，问你最少要购买几套衣服。
本题的难点在于处理是否要脱衣服，如果不用脱的话在原来的结果上+1即可，如果要脱衣服的话，我们需要考虑对后面的各种影响，所以这是我们考虑从后面往前推，以dp[i][j]表示从第i天到第j天的影响，如果不需要脱第i天的衣服，那么我们直接用dp[i-1][j]+1即是dp[i][j]的大小，如果要脱到第i天的衣服，那么我们需要在第i+1到j天之间找到一个第k天穿的衣服和第i天的衣服一样，则dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k][j]),第i到第j天的衣服数量为第i+1到第k-1天的衣服数量+第k到第j天的衣服数量可能大于dp[i+1][j]+1,所以要取两者最小值，为什么不是dp[i][k-1]+dp[k][j]呢，因为dp[i][i]和dp[j][j]是重叠的，即二者只需要买一次即可。
AC代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;const int N = 1e2 + 10;int a[N],dp[N][N];int main() {ios::sync_with_stdio(false);int t,Case=0;cin >> t;while (t--) {int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = n; i >= 1; i--) {for (int j = i; j <= n; j++) {dp[i][j] = dp[i + 1][j] + 1;//使初始值为1for (int mid = i + 1; mid <= j; mid++) {if (a[i] == a[mid]) {dp[i][j] = min(dp[i][j], dp[i + 1][mid - 1] + dp[mid][j]);}}}}printf("Case %d: %d\n", ++Case, dp[1][n]);}
}