题意：给你一个字符串，请把字符串压缩的尽量短，并且输出最短的方案。

例如：AAAAA可压缩为5(A), NEERCYESYESYESNEERCYESYESYES可压缩为2(NEERC3(YES))。

思路：区间DP，设dp[i][j]是把区间[l, r]内的字符压缩之后的最短长度，那么可以想到区间[l, r]可以通过两种方式转换而来：

1 ：[i, j]整个区间本来就可以被压缩

2 ：由2个子区间合并而来。

第二种转换是区间DP的常见操作，第一种直接暴力枚举可重叠串的长度即可。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
            using namespace std;string dp[110][110], s;string _to_string(int num) { string ans; while(num) { ans += num % 10 + '0'; num /= 10; } reverse(ans.begin(), ans.end()); return ans;} int main() { int n; while(cin >> s) { n = s.length(); for (int i = 0; i < n; i++) { dp[i][i] = s[i]; } for (int len = 2; len <= n; len++) { for (int i = 0; i < n - len + 1; i++) { int j = i + len - 1; dp[i][j] = s.substr(i, j - i + 1); for (int nowl = 1; nowl <= len / 2; nowl++) { if(len % nowl) continue; int l = i, r = i + nowl; while(s[l] == s[r] && r <= j) l++, r++; if(r > j) { int num = len / nowl; dp[i][j] = _to_string(num); dp[i][j] += "("; dp[i][j] += dp[i][i + nowl - 1]; dp[i][j] += ")"; //cout<< dp[i][j] <
           
             dp[i][k].length() + dp[k + 1][j].length() || dp[i][j].length() == 0) { dp[i][j] = dp[i][k] + dp[k + 1][j]; } } } } cout << dp[0][n - 1] <