Korder LCS(longest common subsequnce)

#1

why my code is showing run errror during submission ;
otherwise for custom input it is running fine

#2

hello @

image
here it should be
dp[i][0]=0 ;

and dp[0[[j]=0;

also use <= in place of <

#3

but why ?
can you explain it

#4

yeah sure,
see we have n X m matrix .
now dp[i][0] is the case where we have considered string of lenght i and another string of length 0.
so what answer it should have.
it should be 0.
dp[i][0]

now what are the possible values of i .
i can be from 0 to n .
because we can have 0 length string or atmost n length string.

same explanation is for
dp[0][j]=0
whrere j can take value from 0 to m .

#5

but code is still not passing the test cases?

#6

hey the dp states are also wrong.
Define a 3D matrix dp[][][], where dp[i][j][k] defines the Longest Common Subsequence for the first i numbers of first array, first j number of second array when we are allowed to change at max k number in the first array.
Therefore, recursion will look like

image
image891×271 4.29 KB

Printing 1 for each case, i don't know the problem is with my code or with cb ide
#7

but I use a bottom up approach , which is very similar to which I used in norml LCS

can you tell me whats the fault in my approach and code

#8

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.

#9

the dp states are not . correct,
first try to comeup with recurrence relation .and then apply dp of ur choice.