LCS

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
mich
New poster
Posts: 3
Joined: Sun Jun 04, 2006 9:16 pm

LCS

Post by mich »

Hello,

Can anybody help me find the flaw in my LCS algorithm:

Code: Select all


int LCS(int a, int b) {

	if(a >= (int)s1.size() || b >= (int)s2.size() ) return 0;
	if(cache[a][b] != -1) return cache[a][b];

	if(s1[a] == s2[b]) {
		return 1+LCS(a+1,b+1);
	}
	int answer = max(LCS(a+1, b), LCS(a, b+1));
	cache[a][b]=answer;
	return answer;
}
I tried it with two LCS problems(10192 and 10405) and I get WA for both.

Thanks :)
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

It looks correct to me.
Post Reply

Return to “Algorithms”