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


  • 3
    7

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

  • 0

    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


  • 0
    7

    @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!


Log in to reply
 

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