OJ Board

Posted: **Sat Oct 07, 2006 6:55 pm**

i code DP(LCS)using memoization

i am facing a problem in how to find the sequence it self

not how long is it

my function works fine in getting the length of the sequnce

but i dont know how to get the sequence please can anyone help me

here is my function

int LCS (int i , int j)
{

if(i >= len1 || j >= len2)

return 0;

int &r = dp[j];
if( r ! = -1 )
return r;

int r1 = 0 , r2 = 0 , r3 = 0;
if( s1 == s2[j] )
r1 = f ( i + 1 , j + 1) + 1;

r2= f( i , j + 1 );
r3= f( i + 1 , j );

return r=max(r1,r2,r3);
}

Posted: **Sat Oct 07, 2006 8:51 pm**

For example, in this way:

Code: Select all

string lcs(int i, int j) {
	if (i >= len1 || j >= len2)
		return "";
	else if (s1[i] == s2[j])
		return s1[i] + lcs(i+1, j+1);
	else if (LCS(i+1, j) > LCS(i, j+1))   // LCS(i,j) is the function from your code
		return lcs(i+1, j);
	else
		return lcs(i, j+1);
}

OJ Board

Help with DP

Help with DP