LCS

[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]

It looks correct to me.