Longest Common Subsequence

dynamic.py

def lcs_dp(X,Y, m,n):
    dp_arr = [[None]* (n+1) for _ in range(m+1)]
    for i in range(0, m+1):
        for j in range(0,n+1):
            if i == 0 or j == 0:
                dp_arr[i][j] = 0
            elif X[i-1] == Y[j-1]:
                dp_arr[i][j] = 1 + dp_arr[i-1][j-1]
            else:
                dp_arr[i][j] = max(dp_arr[i-1][j],dp_arr[i][j-1])
    return dp_arr[m][n]

Naive.py

def lcs(X,Y, m, n):
    if m < 0 or n < 0:
        return 0
    elif X[m] == Y[n]:
        return 1 + lcs(X,Y, m-1,n-1)
    else:
        return max(lcs(X,Y,m-1,n),lcs(X,Y,m,n-1))