Length of longest common sub sequence

#1

plz tell me why my code is not correct i m using recursion with memorisation (top down dp)

problem : https://online.codingblocks.com/app/player/39658/content/77367/766/video

The problem is in the video

code : https://ide.codingblocks.com/s/213716

test case :
nemato
empty

my code is showing 2 but answer is 3.

Also if I rempve the memorisation (I.e only recursion) then my code works fine .
Plz help and reply asap .

#2

@sengarankit98 generally dp[i][j] represents the LCS of s1 from 0 to i and s2 from 0 to j. But here according to the your recursive conditions , it is not doing anything like this, it is just calling the next recursive case, the values saved in your dp array dont match with the furthur requirements and hence the values in your dp array is wrong thats why it will give wrong answer.
Suggestions:-

  1. Try to start i and j values from the last index of the strings and move accordingly.
  2. Dont initialize your dp array with 0, do it -1, as 0 is one of the possible answers.
#3

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.