Top down longest common subsequence

#1

how is relation is dp[i]=1+dp[i-1][j-1] it should be 1+dp[i+1][j+1] as we used this one in top down approach please explain??

#2

@shampblocks due to recursive nature, top-down DP depends upon states ahead!, but in bottom up you are filling states from 0,0 hence you cannot do

as dp[i+1][j+1] is not calculated yet!
so it is dependent only on previous states!
You can do this way if you do bottom up in reverse fashion (from m,n to 0,0)

#3

i have filled my dp table in reverse order from last column row pair to the pair0,0 and anser is in this 0,0 pair is it fine??

#4

Yes this is also fine!

#5

but i want to know how we conclude in an problem that we can also fill the table from up to bottom?? as in this problem??

#6

There is no formula for it!, you have to visualize the working, as in this case even if you reverse both strings, your answer remains same! hence this works for given problem

#7

so it depends on problem to problem right??

#8

Absolutely it does depends on problem

#9

if i also want to print the lcs how to modify this algorithm??

#10

For this you just first get your dp table, then just start from 0,0 and go for max(dp[i+1][j], dp[i+1][j+1], dp[i][j+1]) ,whenever you move to dp[i+1][j+1], this means that a character is matched so just add that character to your answer! Proceed with this unless you reach m,n.

#11

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.