题目描述
给出一个序列，每次可以给一段染成同一种颜色，问最少要染多少次能够染成给定方案。
输入
输入仅一行，包含一个长度为n的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。
输出
仅一行，包含一个数，即最少的涂色次数。
样例输入
RGBGR
样例输出
3
题解
区间dp
设$f[i][j]$表示染$[i,j]$这段区间所需要的最小次数。
那么当$i$和$j$颜色相同时，显然需要一起染，可以推知$f[i][j]=min(f[i-1][j+1]+1,min(f[i+1][j],f[i][j-1]))$
当$i$和$j$颜色不同时，不能一起染，枚举中间点$k$，相当于染$[i,k]$和$[k+1,j]$两端区间，那么$f[i][j]=min{f[i][k]+f[k+1][j]}$
时间复杂度$O(n^3)$
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 55
using namespace std;
int f[N][N];
char str[N];
int main()
{
int n , i , j , k , l;
scanf("%s" , str + 1) , n = strlen(str + 1);
memset(f , 0x3f , sizeof(f));
for(i = 1 ; i <= n ; i ++ ) f[i][i] = 1;
for(l = 2 ; l <= n ; l ++ )
{
for(i = 1 ; i <= n - l + 1 ; i ++ )
{
j = i + l - 1;
if(str[i] != str[j])
for(k = i ; k < j ; k ++ )
f[i][j] = min(f[i][j] , f[i][k] + f[k + 1][j]);
else f[i][j] = min(f[i][j] , min(f[i + 1][j - 1] + 1 , min(f[i + 1][j] , f[i][j - 1])));
}
}
printf("%d
" , f[1][n]);
return 0;
}