Hi,
I tried to solve the LCS problem in the Atcoder Educational DP Contest. I used the top down approach (recursion + memoization) for solving the problem. I implemented this in Python first, which resulted in a TLE (no surprise, there). Then, I tried implementing the same code in C++, which performed even worse than my Python submission for some reason.
I would like to know where I could improve on further (both in Python and C++), so that the code passes within the time limit. Is it possible for solutions of the top-down approach to pass under the time limit given in the question?
Strings (string s, string t) are copied every time. That leads to additional n-factor. Use references (string &s, string &t) instead.
UPD. Moreover, it is a bad idea to keep the whole answer in every element of dp. Keep [one char + pointer to the previous state] instead.
tch1cherin I tried introducing references to the code. But, it still doesn't come under the time limit. Regarding the [char + pointer] nethod, would you be able to show an implementation for the same? I mostly code in Python and have very liitle experience in C++ at the moment.
For each spot, because of how the dp transitions work, for $$$\textrm{dp}[i][j]$$$ you either add one character when $$$s[i]=t[j]$$$ or skip one of the characters $$$s[i]$$$ or $$$t[j]$$$. Do the following:
_) in $$$\textrm{best}[i][j]$$$ and store $$$(i-1,j)$$$ in $$$\textrm{prev}[i][j]$$$When you want to reconstruct your string, start with $$$(i,j) = (n-1,m-1)$$$ and go to $$$(i,j) := \textrm{prev}[i][j]$$$, storing $$$\textrm{best}[i][j]$$$ whenever it's not that special character.