The request of the problem is printing out the LCS of two strings. Then I submitted my solution to AtCoder, the result returned from OJ was RE or TLE. Ensuring that there is no boundary violations occurred and time complexity is O(lens1 * lens2), I can't find out where is wrong..... Help me plz.
string dp[3010][3010];
void solve()
{
string s1, s2; cin >> s1 >> s2;
s1 = ' ' + s1; s2 = ' ' + s2;
int lens1 = s1.length() - 1, lens2 = s2. length() - 1;
for(int i = 1; i <= lens1; i++)
{
for(int j = 1; j <= lens2; j++)
{
if(s1[i] == s2[j])
dp[i][j] = dp[i - 1][j - 1] + s1[i];
else
{
if(dp[i - 1][j].length() > dp[i][j - 1].length())
dp[i][j] = dp[i - 1][j];
else dp[i][j] = dp[i][j - 1];
}
}
}
cout << dp[lens1][lens2] << endl;
}
This is the part which is causing TLE in tour code. Since N can be upto 3000 and you are running 2 for loops so it becomes 9 * 10^6 = 10^7 (approx). Till here it is fine but you are also copying string of previous dp state in current state which is taking extra O(string length) time inside your loops. For dp[i][j] = dp[i-1][j-1] + s1[i] first your code copies the string in dp[i-1][j-1] in dp[i][j] then it adds an extra character to it and copying and pasting a string takes O(n) times.
OK, fine, thanks!