题意

现在给你一块长度为5的木板，给他涂色，一共有五种颜色，每一次涂色是可以选择涂连续的一段，即我可以涂一格，也可以涂两个连在一起的，也可以涂三格连续在一起的，现在给出目标状态，问要涂的最少次数。

解析

首先我们先分析一下样例是什么意思，样例1：AAAAA，很明显，就是选择颜色A,然后涂一次从最左边涂到最右边这就是最少的次数，

然后是样例二，RGBGR，三次是怎么涂的也不难理解，首先是是涂一次全部涂成R从最左边涂到最右边，即RRRRR，然后选择颜色G从第二个涂到第四个，即RGGGR，最后再涂中间这个，涂成B，就有了RGBGR。

我们可以选择使用区间dp，区间的左端点和右端点的颜色相同的话我们就可以直接给他涂上

如果不相同，那么我们就要枚举分割点k，在到,和到分别涂好然后累加再求一次最小的min就可以了。

所以我们可以得到递推方程，当左端点等于右端点时，即有

左端点不等于右端点时，

最后的即就是最后的答案

还有一个点我也是很无语，题目说的是长度为5的木板，输入描述里又变成了长度为n，这个地方卡了我好久。。。。无语是真的

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100;
int dp[MAXN][MAXN];
string s;

int main(void){
    cin>>s;
    int len=s.size();
    s='#'+s;
    for(int i=0;i<MAXN;++i)
        for(int j=0;j<MAXN;++j)
            dp[i][j]=0xfff;
    for(int i=1;i<=len;++i)
        dp[i][i]=1;
    for(int i=2;i<=len;++i){
        for(int l=1;l+i-1<=len;++l){
            int r=l+i-1;
            if(s[l]==s[r])
                dp[l][r]=min(dp[l+1][r],dp[l][r-1]);
            else
                for(int k=l;k<r;++k)
                    dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);            
        }
    }
    printf("%d\n",dp[1][len]);
    return 0;
}