区间DP好题，看到这题很容易想到设 \(f[i][j]\) 为区间 \(i\)~\(j\) 内的最短折叠，那么转移方程就为：
\[f[i][j]=min_{k=i}^{j-1}(f[i][j],f[i][k]+f[k+1][j]) \]然鹅这个转移方程是错误的，举个栗子。对于一个字符串aaabcbcaaabcbc，aaaMbcRaaaMbcR是它的一个合法折叠，但MaaaMbcRR却不是，因为这时候的R对应的并不是第一个M，而是第二个。因此要做出改进。
设 \(f[i][j][0]\) 为区间 \(i\)~\(j\) 内不含M的最短折叠，\(f[i][j][1]\) 为区间 \(i\)~\(j\) 内含M的最短折叠。那么改进后的状态转移方程为：
对于可以折叠的区间有
\[f[i][j][0]=min(f[i][j][0],f[i][\frac{i+j}2][0]+1) \]AC代码：
#include <bits/stdc++.h>
#define R register
using namespace std;
int n,f[55][55][2];
string s;
bool check(int l,int r){
int mid=l+r>>1;
for(int i=l;i<=mid;i++)if(s[i]!=s[mid+i-l+1])return false;
return true;
}
int main(){
cin>>s;n=s.size();
s=' '+s;
memset(f,0x7f,sizeof(f));
for(int i=1;i<=n;i++)f[i][i][0]=f[i][i][1]=1;
for(R int len=2;len<=n;len++)
for(R int i=1;i+len-1<=n;i++){
R int j=i+len-1;
if(!((j-i+1)&1)&&check(i,j))f[i][j][0]=min(f[i][j][0],f[i][i+j>>1][0]+1);
for(int k=i;k<j;k++)f[i][j][0]=min(f[i][j][0],f[i][k][0]+j-k);
for(int k=i;k<j;k++)f[i][j][1]=min(f[i][j][1],min(f[i][k][0],f[i][k][1])+min(f[k+1][j][0],f[k+1][j][1])+1);
}
printf("%d",min(f[1][n][0],f[1][n][1]));
return 0;
}