hey guys this is my dynamic programming
tutorial with the longest common
subsequence problem as our example now
let me explain what the longest common
subsequence problem is we have two
strings let's call it P and Q and we're
trying to find a common string and we're
trying to find the longest one of course
and in this case that would be B a D and
one thing to note here is that these
characters are not necessarily
contiguous we're going to solve this
problem using dynamic programming but
let's first talk about this general
procedure that we have that we can use
for solving any dynamic programming
problems so the first step is to come up
with a recursive solution and then we
memorize the intermediate results or
restore the intermediate results to make
you run faster and finally we can come
up with something called a bottom-up
approach and I'm going to explain what
it means later this is an optional step
by the way here's a recursive solution
we're going to write this function LCS
longest common subsequence of p0 and q0
the two input strings and we're going to
return the length of the longest common
subsequence instead of the subsequence
itself so with our previous example
we're going to return instead of BA D
we're going to return the length of it
which is 3 the idea behind any recursion
is that of course we're going to take
down this problem into smaller problems
and we're going to solve those instead
and there are two cases we need to
consider for that the first case is when
p 0 and Q 0 and with the same character
let's call it let's just call it X and
there are some preceding characters
let's call them P 1 and Q 1 they could
be any lengths they could be empty or
non empty what we say in this case is
that the longest common subsequence of p
0 and Q 0 must end with X and so we'll
get rid of these and we'll find the LCS
of p1 and
q1 and we'll append it there before X
and that's going to be our longest
common subsequence so that's expressed
as LCS of p 0 and Q 0 is equal to 1
which comes from X plus LCS of p1 and q1
the second case is when p 0 and q0 don't
end with the same character so let's
just call those characters x and y and
again there are some preceding
characters before x and y let's call
them p1 and q1 again that could be any
length and what we do in this case is
we'll say okay let's just get rid of one
of the characters let's just say X and
we will find the LCS of p1 and Q 0 which
is what I wrote here and we'll do the
same thing with Y and find the LCS of p0
and q1 and we'll take the longer one of
those so that's expressed as LCS of p 0
Q 0 is equal to maximum or the larger
one of those here's a recursive solution
in code we define the function LCS of PQ
n m and N and M those are integers
they're here because I don't want to
recreate strings every time I call this
function here's what I mean so let's say
P equals ABC and we have N equals 2 then
instead of looking at the whole string
we'll just look at the first two
characters and it's the same thing with
Q and M if Q is ABC and M is 1 we'll
just look at the first character so this
way we don't have to reproduce strings
every time and here's our base case if N
equals 0 or M equals 0 that means we're
looking at an empty string so we'll just
return 0 and I'm storing this result in
the result variable and returning it
here if that's not the case and if the
first care if the last character of p
and the last character q are the same
we'll just return 1 plus LCS
of PQ n minus 1 n minus 1 and if that's
not the case the last characters are not
going to be the same but I wrote this
just for clarity and what we're going to
do here is take LCS or PQ n minus 1 m
and LCS of PQ and M minus 1 and we'll
take the maximum one of those and return
that here's a quick analysis over a
recursive solution we'll look at one of
the worst case scenarios when P and Q
don't have any characters in common and
we'll look at this particular example
when P equals a a and Q equals BV B
first we will call LCS of P Q 2 3
because we have two characters of three
characters and to find that we need to
call LCS of P Q 1 3 as just abbreviated
as L 1 3 and we'll also need to call L 2
2 and to find L 1 3 we need to call L 0
3 which is a base case and I want to and
so that's what this diagram shows and as
you can see the problem with this
approach is that there are a lot of
duplicates in our computation so we are
computing L 1 2 twice the exact same
competition and we're computing L 1 1 3
times and that's why this is very
wasteful and it's very slow in fact the
time it takes to find the original LCS
is about an order of two to the power of
n plus m in the worst case scenario and
dynamic programming says why not just
store all those intermediate results so
we can make this function run faster so
now that we found a recursive solution
we're going to memorize or store the
intermediate results to make our
function round faster
here's a memorized version over previous
recursive function the only things that
changed from the previous function are
these three lines and what we're doing
here is we are storing the intermediate
results in this array in
two dimensional array of height and and
with em and every time this function is
called we ask ourselves do we or do we
already have this result so we're
initializing each element to undefined
and we ask ourselves do we already have
it and if we already have the
intermediate results if this is not
undefined or if it's already defined
then return that instead of going
through the whole function and if that's
not the case we go through the whole
function find the result but before we
return it we store it in this array so
what's the runtime for this one thing
you can see right here is that we reach
this last line only at most n M times
because that's the number of variable
combinations we have the possible
variable combinations we have and so we
go through this whole function only at
most n M times and in this part we call
LCS at most twice so the number of
recursive calls is at most two n m times
and each time the time it takes to
execute each call is a constant time so
the whole time complexity is an order of
n times M which is much better than what
we had before so we found a recursive
solution and we memorized intermediate
results and now we can come up with a
bottom up solution which is an optional
step in our recursive and memorized
solutions what we did was let's just say
for this particular example P equals a a
and Q equals a B what we did was we
called LCS of P Q 2 3 and we said ok to
find this we need to call LCS of P Q 1 3
and LCS of P Q 2 2 and so on so we
started at the top and we went down so
it's a top
down approach we can also use a
bottom-up approach so start with M
equals 0 and N equals 0 and ask
ourselves what LCS of P Q 0 0 that's
what that's of course zero and these are
going to be all zeros and we can fill
out this whole table
so what's LCS of P Q 1 1 for that one
we'll be comparing just these two
characters so that's going to be 1 in
the code we are actually using these the
information from here and same thing
with N equals 1 M equals 2 we're
comparing these three characters so
that's going to be one that comes from
this part so we're going to fill out
this whole table that way
once we fill out this whole table we can
just look at the last value N equals 2
and M equals 3 and that's the value we
want in the first place all right
hopefully you liked the video if
anything was unclear please let me know
and if you like this one you might also
like this other video I have about
dynamic programming with Fibonacci
sequence and if you want to watch more
videos like this one you can just
subscribe right here and thanks so much