Show step by step tabular dynamic programming solution for LCS problem for the given sequences code example
Example 1: python lcs length
def lcs(X, Y):
n = len(Y)
m = len(X)
L = [[None]*(n + 1) for i in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0 or j == 0 :
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1]+1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
return L[m][n]
Example 2: longest common subsequence
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
"""
text1: horizontally
text2: vertically
"""
dp = [[0 for _ in range(len(text1)+1)] for _ in range(len(text2)+1)]
for row in range(1, len(text2)+1):
for col in range(1, len(text1)+1):
if text2[row-1]==text1[col-1]:
dp[row][col] = 1+ dp[row-1][col-1]
else:
dp[row][col] = max(dp[row-1][col], dp[row][col-1])
return dp[len(text2)][len(text1)]