Please Help Me! This is a typical Lcs Problem!

Правка en2, от KomorGiaoGiao, 2024-09-16 15:22:45

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский KomorGiaoGiao 2024-09-16 15:22:45 3 Tiny change: 'd from OJ is RE or TL' -> 'd from OJ was RE or TL'
en1 Английский KomorGiaoGiao 2024-09-16 15:21:48 877 Initial revision (published)