OJ Board

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