In Python

Use recurrence to design a tabulation-based DP algorithm for the length of common subsequence (LCS) problem. The function LCS takes in two variables: string 1 and string 2.

LCS length between prefix of 1 of length and prefix of 2 of length , for 0 = |1| ,0 = |2|. Call this quality [,].

Skeleton Code:

import sys

def lcs(s1, s2):

# Put code here

return None

s1 = "ATGC" s2 = "AAGTC"

print(lcs(s1, s2))

Initialize (m+1)(n+1) array LCS. FORi=0,,m:FORj=0,,nLCS[i,j]:=0LCS[i1,j1]+1max(LCS[i1,j],LCS[i,j1])ifi=0orj=0ifi,j>0andS1[i]=S2[j],ifi,j>0andS1[i]=S2[j]