DZY 's BLOG

类似记忆化dp、、

f[i][j]表示i~j这一段最少要涂几次。每次递归计算、头尾如果相同可以最先涂、所以可以减1、然后合并上来就行、、

最近写的代码怎么都这么短？还是我太弱了只会刷水？唉、、囧、、、

#include<cstdio>
#include<algorithm>
#include<cstring>
const int inf=1000000009;
int F[60][60]={0},l;    char s[60];
int f(int l,int r){
    if(l==r)    return 1;   if(F[l][r]) return F[l][r]; F[l][r]=inf;
    for(int i=l;i<=r;i++)   F[l][r]=std::min(f(l,r),f(l,i)+f(i+1,r));
    return F[l][r]-=(s[l]==s[r]);
}int main(){
    scanf("%s",s);  l=strlen(s);    printf("%d\n",f(0,l-1));   return 0;
}