Longest Common Subsequences (LCS)

(i). LCS -Recursive

Python Code


def lcs(x,y,m,n):
    if m ==0 or n ==0: return 0
    if x[m-1] == y[n-1]:
        return 1+lcs(x,y,m-1,n-1)
    else:
        return max(lcs(x,y,m-1,n),lcs(x,y,m,n-1))
        

x = 'abcdef'
y = 'abcdef'

m = len(x)
n = len(y)

res = lcs(x,y,m,n)
print(res)

(ii). LCS - Memoization(TOP DOWN)

Python Code


text1 = 'abcde'
text2 = 'abcgh'
m = len(text1)
n = len(text2)
dp = [[-1] * (m+1) for _ in range(n+1)]  
def lcs(s1, s2, m, n):
    if dp[n][m] != -1:  
        return dp[n][m]  
    if m == 0 or n == 0:
        dp[n][m] = 0
    elif s1[m - 1] == s2[n - 1]:
        dp[n][m] = 1 + lcs(s1, s2, m - 1, n - 1)
    else:
        dp[n][m] = max(lcs(s1, s2, m - 1, n), lcs(s1, s2, m, n - 1))
    return dp[n][m]  
      
res = lcs(text1, text2, m, n)
print(res)

(iii). LCS - Tabulation(Bottom UP)

Python Code


text1 = 'abcdef'
text2 = 'abcdef'
m = len(text1)
n = len(text2)
dp = [[0] * (m+1) for _ in range(n+1)]  
def lcs(s1, s2, m, n):
    for i in range(m+1):
        for j in range(n+1):
            if i==0 or j==0:
                dp[i][j] = 0
    
    for i in range(1,m+1):
        for j in range(1,n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i][j-1],dp[i-1][j])
    return dp[m][n]
res = lcs(text1, text2, m, n)
print(res)

1. LCS -Find length

Python Code


text1 = 'abcdef'
text2 = 'abcdef'
m = len(text1)
n = len(text2)
dp = [[0] * (m+1) for _ in range(n+1)]  
def lcs(s1, s2, m, n):
    for i in range(m+1):
        for j in range(n+1):
            if i==0 or j==0:
                dp[i][j] = 0
    
    for i in range(1,m+1):
        for j in range(1,n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i][j-1],dp[i-1][j])
    return dp[m][n]
res = lcs(text1, text2, m, n)
print(res)

2. Coin Chnage-I

Python Code


#Unbounded Knapsack Coin change I
arr = [1,2,3]
n = len(arr)
sum = 5

dp = [[0]*(sum+1) for _ in range(n+1)]
		
for i in range(0,n+1):
    dp[i][0] =1
for i in range(1,n+1):
    for j in range(sum+1):
        if arr[i-1]<=j:
            dp[i][j] = dp[i][j - arr[i-1]] + dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j]
res = dp[-1][-1]
print(res)

3. Count of subset sum

Python Code


def count(arr,n,sum):


    dp = [[0]*(sum+1) for _ in range(n+1)]
            
    for i in range(0,n+1):
        dp[i][0] =1
    for i in range(1,n+1):
        for j in range(sum+1):
            if arr[i-1]<=j:
               dp[i][j] = dp[i-1][j - arr[i-1]] + dp[i-1][j]
           else:
               dp[i][j] = dp[i-1][j]
    return dp[-1][-1]%mod

arr = [1,2,3,4]
n = len(arr)
res = count(arr,n,sum(arr))
print(res)