【题解】LuoGu4170：[CQOI2007]涂色

原题传送门
区间$dp$
令$d{p}_{i,j}$表示涂$i-j$的最小次数
转移：

• $d{p}_{i,i}=1$
• $d{p}_{i,j}=min(d{p}_{i,j+1},d{p}_{i+1j})(s_i=s_j)$
• $d{p}_{i,j}=min(d{p}_{i,j},d{p}_{i,k}+d{p}_{k+1,j})(s_i!=s_j)$

Code：

#include <bits/stdc++.h>
#define maxn 100
using namespace std;
int dp[maxn][maxn];
char s[maxn];

int main(){
	scanf("%s", s + 1);
	int n = strlen(s + 1);
	memset(dp, 0x3f, sizeof(dp));
	for (int i = 1; i <= n; ++i) dp[i][i] = 1;
	for (int l = 1; l <= n; ++l){
		for (int i = 1, j = 1 + l; j <= n; ++i, ++j){
			if (s[i] == s[j]) dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]);
			else for (int k = i; k < j; ++k) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
		}
	}
	printf("%d\n", dp[1][n]);
	return 0;
}