Inspired by @amaximov

`DP[i][j]`

best result that begins with index i of length j

`mDP(DP,s,i,j)`

memoization DP, calculate `DP[i][j]`

IDEA:

Each optimal `DP[i][j]`

is either:

1: totally divided by some substring; (first loop, `O(n^(1.5))`

thanks to @yaopiupiupiu)

2: sum of optimals of two substrings. (second loop, `O(n)`

)

In total, we will only call `mDP`

`n^2`

times, so complexity is `O(n^3.5)`

.

```
class Solution {
void mDP(vector<vector<string> >& DP,string s,int i, int j){
DP[i][j]=s.substr(i,j);
//first loop
for(int k=1;k<j;k++){
if(j%k==0){
int fine=true;
for(int kk=1;kk<j/k;kk++){
if(!(s.substr(i,k)==s.substr(i+kk*k,k))){
fine=false;
break;
}
}
if(fine){
if(DP[i][k].size()==0)mDP(DP,s,i,k);
for(int kk=1;kk<j/k;kk++)DP[i+kk*k][k]=DP[i][k];
if(DP[i][j].size()>to_string(j/k).size()+2+DP[i][k].size()){
DP[i][j]=to_string(j/k)+"["+DP[i][k]+"]";
}
}
}
}
//second loop
for(int k=1;k<j;k++){
if(DP[i][k].size()==0)mDP(DP,s,i,k);
if(DP[i+k][j-k].size()==0)mDP(DP,s,i+k,j-k);
if(DP[i][j].size()>DP[i][k].size()+DP[i+k][j-k].size()){
DP[i][j]=DP[i][k]+DP[i+k][j-k];
}
}
}
public:
string encode(string s) {
int l=s.size();
vector<vector<string> > DP(l,*new vector<string>(l+1,""));
mDP(DP,s,0,l);
return DP[0][l];
}
};
```