LCS problem from Atcoder Edu-Dp gives TLE despite caching, into memo table

help
, ,
1

Below Top down, approach is giving me TLE for Atcoder Educational Dp contest’s LCS problem, despite memoizing it gives TLE, take a look.

string LCSUtil(vector<vector<string>>&Cache,string &lcs,string s,string t,int si,int ti){
      if(si>=s.length() or ti>=t.length()) return "";
      if(Cache[si][ti]!="NULL") return Cache[si][ti];
      if(s[si]==t[ti]) return Cache[si][ti] = (lcs+s[si]+LCSUtil(Cache,lcs,s,t,si+1,ti+1));
      string first = LCSUtil(Cache,lcs,s,t,si+1,ti);
      string second = LCSUtil(Cache,lcs,s,t,si,ti+1);
      return Cache[si][ti] =  ((first.length()>second.length())?first:second);
    }

    void LCS(){
      string s,t;
      cin>>s>>t;
      vector<vector<string>>Cache(s.length(),vector<string>(t.length(),"NULL"));
      string lcs = "";
      cout<<LCSUtil(Cache,lcs,s,t,0,0)<<'\n';
    }

Problem link LCS-Atcoder Edu-Dp

2

Hi Pawan_31,

I also ran into the same issue on Atcoder. It’s not just LCS question that gives TLE but just about any DP question that uses memoization (or caching) instead of bottom-up DP gives TLE.

If you watch any DP tutorial, it will tell you that bottom-up DP is same as top-down (or memoized) DP but people actually prefer bottom-up DP, that is the truth. One reason is because top down DP uses extra space on the recursive call stack whereas bottom-up DP does not. Also, bottom-up DP can be fine tuned sometimes to use O(1) extra space.

For eg: Consider the elementary Nth fibonacci number introductory DP problem.
You can write it as: f(n) = f(n-1) + f(n-2) and cache the result but every recursive call uses O(n) space on the recursion call stack in addition to the Cache[] data structure that stores the results.

But if you used bottom-up DP, you can do it as simply:
f1 = 0
f2 = 1
for (int i=2; i <= n; i++) {
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
return f3;