# C++ 89ms DP memoization O(n^3.5)

• 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];
}
};
``````

• thanks for your sharing, but I am thinking about that the first loop is not O(n^0.5). as actually in

``````        for(int k=1;k<j;k++){
if(j%k==0){
for(int kk=1;kk<j/k;kk++){
if(!(s.substr(i,k)==s.substr(i+kk*k,k))){
//...
}
}
//...
}
}
``````

the two for-loops actually works for at least O(j) time, eg. when (k == 1), kk = [1..j).
also substr is not O(1), it's `Unspecified, but generally linear in the length of the returned object.` //from C++ reference

• @yaopiupiupiu Yeah, I think your are right. I think I forgot the inner loop, but `substr` won't make difference here, as the comparison takes also linear time. I believe it is actually `O(Number_of_divisors * Length_of_string)` which is bounded by `O(n^1.5)`, which seems cumbersome.
Thanks!
What's more, so far, I can not see how to reduce this complexity but it seems to me that it's kind of huge. I would be glad to hear if there is any idea to improve it!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.