LightOJ 1422 Halloween Costumes 구간 DP

제목: n일 동안 따로 입을 옷을 줄 테니 껴입어도 되지만 일단 벗으면 다시 입을 수 없으니 n일 동안 몇 벌의 옷을 준비해야 하는지 물어본다.
처음으로 구간 DP를 만들었는데, 문제풀이들을 보면서 한참을 생각하다가 orz를 깨닫게 됐는데...
dp[i][j]는 i일째부터 j일째까지 최소한의 옷을 입기 위해 i일째를 고려한다. 만약에 뒤에 [i+1, j]일의 옷을 상관하지 않는다면 dp[i][j]=dp[i+1][j]+1.
그리고 구간 [i+1,j]에서 i일차 옷과 같은 날을 찾아 그날까지 i를 벗지 않으려고 시도한다.
그러면 dp[i][j]=dp[i+1][k-1]+dp[k][j]가 될 수 있다. 너는 아마 이튿날 없어졌다는 것을 발견할 수 있을 것이다. 사실 +양쪽만 바꾸면 된다. 바로 이튿날 옷을 계속 입고 있는 것이다.
코드:

/*
 *  Author:      illuz 
 *  Blog:        http://blog.csdn.net/hcbbt
 *  File:        loj1422.cpp
 *  Create Date: 2013-11-11 13:53:33
 *  Descripton:  invertel dp 
 */

#include 
#include 

#define min(a, b) ((a) < (b) ? (a) : (b))

const int MAXN = 110;
int dp[MAXN][MAXN], a[MAXN];
int n, t, cas;

int main() {
	scanf("%d", &t);
	for (cas = 0; cas < t; cas++) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);

		for (int i = 0; i <= n; i++)
			for (int j = i; j <= n; j++)
				dp[i][j] = j - i + 1;

		for (int i = n - 1; i >= 1; i--)
			for (int j = i; j <= n; j++) {
				dp[i][j] = dp[i + 1][j] + 1;
				for (int k = i + 1; k <= j; k++)
					if (a[k] == a[i])
						dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k][j]);
			}

		printf("Case %d: %d
", cas + 1, dp[1][n]);
	}
	return 0;
}