Can you please help why i’m getting TLE in this approach:
Submission link:
LCS Atcoder Question Bottom UP approach
hello @rishit517
ur dp state is not efficient.
the dp solution has space complexity -> O(n^3)
and in each transistion u are appending some characters to string which make its time complexity to order of O(N^4).
the idea for this problem is to first find the prepare dp table for lcs lenght
and then use that length to track back the string.
refer this->link
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.