题目描述
假设你有一条长度为 55 的木版，初始时没有涂过任何颜色。你希望把它的 55 个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为 55 的字符串表示这个目标：RGBGR。
每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成 RRRRR，第二次涂成 RGGGR，第三次涂成 RGBGR，达到目标。
用尽量少的涂色次数达到目标。
输入格式
输入仅一行，包含一个长度为 nn 的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。
输出格式
仅一行，包含一个数，即最少的涂色次数。
输入输出样例
输入 #1复制
AAAAA
输出 #1复制
1
输入 #2复制
RGBGR
输出 #2复制
3
说明/提示
40\%40% 的数据满足 1\le n\le 101≤n≤10。
100\%100% 的数据满足 1\le n\le 501≤n≤50。
仔细观察每一次染色的操作对象，是一个连续的范围，这是区间dp最明显的特征, 确定算法核心是区间dp
f[i,j]表示s[i]–s[j]染色成为要的状态的最小次数，当s[i]-s[j]染色成了要的状态，那么s[i]到s[j]之间的状态也已经染成了要的状态，类似石子合并 确定分割点k
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100;
typedef long long LL;
char s[maxn];
LL f[maxn][maxn];int main(void)
{LL n=0;scanf("%s",s+1); n=strlen(s+1);memset(f,0x3f,sizeof(f));//dp求最小值的时候要初始化最大 for(LL i=1;i<=n;i++) f[i][i]=1; for(LL len=2;len<=n;len++)for(LL i=1;i+len-1<=n;i++){LL j=i+len-1;if(s[i]==s[j])f[i][j]=min(f[i+1][j],f[i][j-1]);else if(s[i]!=s[j]){for(LL k=i;k<j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]); } }cout<<f[1][n]<<endl;
return 0;
}