上课讲的，不然也不会做蓝题（ 我的代码：

#include<bits/stdc++.h>
using namespace std;
int dp[110][110],l;
char s[110];
//—————————————————————————— 
int num(int n){//统计括号前数字位数 
	int sum=0;
	while(n!=0){
		sum++;
		n/=10;
	}
	return sum;
}//
//—————————————————————————— 
bool check(int ll,int rr,int kk){//判断字符串是否成规律 (左，右，规律字符 
	if((rr-ll+1)%(kk-ll+1))return false;//不能整除则成不了规律 
	for(int p=kk+1;p<=rr;){//除去规律字符串，将剩下的一一比对 
		for(int f=ll;f<=kk;f++){//规律字符串 
			if(s[f]!=s[p])return false;//如果不同直接返回 
			p++;//f与p同时++ 
		}
		p++; //多加一位 
	}
	return true;//中途不返回，即为成规律 
}//
//—————————————————————————— 
void DP(){//动规算长度 
	for(int i=l;i>=1;i--){//倒 
		for(int j=l;j>=i;j--){
			int cmp=j-i+1; //正在被计算的字符串长度（压缩前可能比压缩后还要短 
			for(int k=i;k<=j;k++){//规律末字符k 
				if(check(i,j,k)){//成规律 
					cmp=min(cmp,num((j-i+1)/(k-i+1))/*多少组规律字符*/+2+(k-i+1));//数字长+括号+循环长 
				}
			}
			dp[i][j]=cmp;//如果压缩成功则为新，失败则不变 
			for(int k=i;k<=j;k++){//存在分界 
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);//分成两半(已遍历 
			}//（分界不存在新压缩，直接赋值 
		} 
	}
}
int main()
{
	memset(dp,0x3f3f3f3f,sizeof(dp));//初始化 
	scanf("%s", s+1);
	l=strlen(s+1);//往后调一位 
    DP();
    cout<<dp[1][l];
	return 0;
}

老师的代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int dp[N][N]; // DP[i,j] 表示区间 [i,j] 压缩后的长度
int len; // 字符串s总长 
char s[N]; // 字符串
//----------------------------------------------------
int num(int x){ // 数字 x 的多少位
	int ret = 0;
	while(x) x /= 10, ret++;
	return ret;
}
//----------------------------------------------------
// 检查区间 [l,r] 有没有 [l,k] 这个循环节
bool check(int l, int r, int k){ 
	// [l,r] 的长度显然需要是 [l,k] 倍数
	if((r - l + 1) % (k - l + 1) != 0) return false; 
	int ll = k - l + 1; // [l,k] 的长度, 例如 YES的长度 
	int tmp = (r - l + 1) / ll; // 区间是否能表示成 tmp(xxx), 例如 3(YES) 
	for(int i = 2; i <= tmp; i++) // 依次检查每个循环节
		for(int j = 1; j <= ll; j++) // 循环节内比对 
			// 只需要比对每一部分是不是和第一个循环节相同 
			// 左边为第 i 个循环节第 j 个字符的位置
			// 右边为第 1 个循环节第 j 个字符的位置
			if(s[l + (i-1)*ll + j - 1] != s[l + j - 1]) 
				return false; // 不一样
	return true; // 一样
}
//  非记忆化搜索版本 
void DP_work(){ 
	// 区间DP的递推版本，需要保证算某个区间的时候，所有它的子区间都计算过了
	// 区间左端点从大到小枚举，右端点随意 
	for(int L=len;L>=1;L--)
		for(int R=L;R<=len;R++){
			// 现在计算 DP[L][R]
			int tmp = R - L + 1; // 第一种转移 dp = r - l + 1
			for(int k = L; k < R; k++) // 第二种转移 X(S) 
				if(check(L, R, k)){//看看 [l,k] 是不是 [l,r] 的一个循环节
					int len_num = num((R-L+1)/(k-L+1)); /*前面数字的长度*/
					tmp = min(tmp, dp[L][k] + 2/*左右括号*/ + len_num);
				}
			for(int k = L; k < R; k++) // 第三种转移，枚举分界点, 分成 ABAB|AAA 
				tmp = min(tmp, dp[L][k] + dp[k+1][R]);
			dp[L][R] = tmp;
		}
}

int main(){
	scanf("%s", s+1); // 读入字符串
	len = strlen(s + 1); // 获得串长
	memset(dp, 0x3f, sizeof(dp)); // 全设置成 INF
//	printf("%d", DP(1, len)); // 记忆化搜索版本 
	DP_work(); // 非记忆化版本 
	printf("%d", dp[1][len]);
}

但没完全抄（？