不难想到区间 DP，令 f_{i,j} 表示将区间 [i,j] 完全折好最少要折多少次，以及在这一前提下最小的不对称度是多少。那么我们枚举在哪个点 k 折叠，并转移即可。能在点 k 折叠要求 k 左右边能完全匹配的位数 p_k\ge\min(k-i,j-k)。这个 p_k 可以 O(n^2) 预处理。总时间复杂度 O(n^3) 的代码。
考虑优化，注意到对于区间的左半边是一类转移，区间的右半边是一类转移。对于剩余串 a 和 b，如果 b 是 a 的子串，那么 b 的最优折叠一定优于 a 的最优折叠。这启示我们，对于区间 [i,j] 左半边的所有 k，取最右边那个，设为 s；右半边的，取最左边那个，设为 t。f_{i,j} 只需要由 f_{s+1,j} 和 f_{i,t-1} 转移而来，这样就可以保证每次操作都是最优的。代码。
注意到 s 的实质是前缀 [1,\lfloor\frac{i+j}{2}\rfloor] 里满足 i\ge k-p_k 的最大 k。状态 (\lfloor\frac{i+j}{2}\rfloor,i) 只有 O(n^2) 个，所以我们可以通过枚举 O(n^2) 预处理出所有 s。对 t 的处理同理。总时间复杂度 O(n^2)，空间复杂度 O(n^2)，跑得很快。代码。