## Memoized LCS and the Table

Recall the memoized version of LCS (here in C++ syntax):

int LLCS(string &X, int m, string &Y, int n, int **T, int **E)
{
if (T[m][n] == -1)
{
if (m == 0 || n == 0)
T[m][n] = 0;
else if (X[m-1] == Y[n-1])
{
E[m][n] = 1;
T[m][n] = 1 + LCS(X,m-1,Y,n-1,T);
}
else
{
int t1 = LCS(X,m-1,Y,n,T);
int t2 = LCS(X,m,Y,n-1,T)
E[m][n] = t1 >= t2 ? 2 : 3;
T[m][n] = max(t1,t2);
}
}
return T[m][n];
}

Break up into groups and run through how LCS
works on input X := dine and Y := tied.
Specifically, keep your eye on table T, and pay attention to the
order in which LCS fills the table T.

When you're done, use the table E to recover the LCS.

## Dynamic Programming and LCS

If you paid attention to the memoized LCS algorithm, you should
have noticed that the recursive structure of LCS ensures that
we don't fill table entry T[i][j] until either T[i-1][j-1] is
filled in (in the case where X[i-1] = Y[j-1]) or
both T[i-1][j] and T[i][j-1] are filled in.

What if we shifted our perspective, and made filling in the
table T (and, ultimately, E as well) our goal. Could we
dispense with the top-down recursive control of the LCS() from
above and just fill in the table with some nested loops?

Let's try it using dine and tied again and see how it might work.
(We did this in class.)

So the moral of the story is that we can, but we have to be
careful! In the memoized version, the recursive control
ensured that we never filled in a table entry before the
entries it relied on were already filled in. Now it's up to
us to carefully fill in the table in an order that ensures the
same thing.

//-- Fill in tables T and E --//
**for**(**int** i = 0; i <= m; i++)
T[i][0] = 0;
**for**(**int** j = 0; j <= n; j++)
T[0][j] = 0;
**for**(**int** i = 1; i <= m; i++)
**for**(**int** j = 1; j <= n; j++)
**if** (X[i-1] == Y[j-1])
**{**
T[i][j] = 1 + T[i-1][j-1];
E[i][j] = 1;
**}**
**else**
**{**
**int** t1 = T[i-1][j];
**int** t2 = T[i][j-1];
**if** (t1 >= t2) **{** T[i][j] = t1; E[i][j] = 2; **}**
**else** **{** T[i][j] = t2; E[i][j] = 3; **}**
**}**

The algorithm we get this way is an example of what is called
"dynamic programming". Check out
lcsdynamicprog.cpp for a full
implemention.