分析
读完题后一眼区间DP
压缩规则分为三类：原子路径（单个字符）、两个压缩路径的连接、单个压缩路径的重复。我们需要找到每个子区间的最优压缩方式，最终得到整个字符串的最短压缩大小。
设 \(dp[i][j]\) 表示字符串从下标 \(i\) 到 \(j\)（闭区间）的最短压缩大小，单个字符的压缩大小为 1，即 \(dp[i][i] = 1\)。
然后就可以有两种转移：
- 分割转移：将区间 \([i,j]\) 拆分为 \([i,k]\) 和 \([k+1,j]（i≤k<j）\)，则 \(dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])\) 。
- 重复转移：若 \([i,j]\) 可由长度为 \(L\) 的子串重复 \(m\) 次构成 \((j-i+1) % L == 0\)，则 \(dp[i][j] = min(dp[i][j], dp[i][i+L-1])\)。
然后整个字符串的最短压缩大小就为 \(dp[0][n-1]\)（字符串下标从 0 开始）。
Code：
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){int n;string s;cin >> n >> s;int dp[700][700];for (int i = 0; i < n; i++){dp[i][i] = 1;}for (int l = 2; l <= n; l++){for (int i = 0; i + l <= n; i++){int j = i + l - 1;dp[i][j] = 1e9;for (int k = i; k < j; k++){dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);}for (int L = 1; L < l; L++){if (l % L){continue;}bool ok = 1;for (int t = 0; t < l; t++){if (s[i + t] != s[i + t % L]){ok = 0;break;}}if (ok) dp[i][j] = min(dp[i][j], dp[i][i + L - 1]);}}}cout << dp[0][n - 1] << endl;return 0;
}