Last week we went over the basics of dynamic algorithms, the definition, and the steps in creating a dynamic program. This week we will walk through an example, we will take a common algorithm and then using our step make it dynamic.
The algorithm we will be working with is Longest Common Subsequence or LCS for short, this and variations on it are a common leet code and white boarding problem so more likely than not you have seen this or will see this algorithm. The basic problem statement is you have two strings for example “Coward” and “Forward”, and you must create and algorithm that finds the longest subsequence of letters that are matched in both words, in this example it would be “oward”. To get to the LCS you would first check all other subsequences such as “Bas” and so on. The non-dynamic or brute force approach will have an exponential time complexity is it will as it will have overlapping subproblems that will result in inefficiency causing it to run in its worst case when both words have no matches at O() and if you know anything about time complexity this is extremely slow. Here is a basic recursive version of the algorithm.
def lcs(X, Y, m, n):
if m == 0 or n == 0:
return 0;
elif X[m-1] == Y[n-1]:
return 1 + lcs(X, Y, m-1, n-1);
else:
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
# Driver program to test the above function
X = "AGGTAB"
Y = "GXTXAYB"
print "Length of LCS is ", lcs(X , Y, len(X), len(Y))
(1)
As you can see this solution is successful at find the LCS, while the code is simple easy to read it is horribly in efficient as it will solve certain parts of the sub problem twice in the recursion tree. This is a great example of a problem to use dynamic programming on as we know DP uses techniques to save results to stop from overlapping subproblems. So, we start on our first step we will identify the sub problem. Luckily, we have already done so in the original version breaking it into sub. We will do this in a bottom up approach, the operations we must do on each LCS word is compare each letter to one another, while also using an array for storing the results to compare to later. Then contain this inside two nested loops as this we will at least need to pass over the strings n times. Here is the DP version of the algorithm.
def lcs(X , Y):
# find the length of the strings
m = len(X)
n = len(Y)
# declaring the array for storing the dp values
L = [[None]*(n+1) for i in xrange(m+1)]
"""Following steps build L[m+1][n+1] in bottom up fashion
Note: L[i][j] contains length of LCS of X[0..i-1]
and Y[0..j-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])
# L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1]
return L[m][n]
#end of function lcs
# Driver program to test the above function
X = "AGGTAB"
Y = "GXTXAYB"
print "Length of LCS is ", lcs(X, Y)
# This code is contributed by Nikhil Kumar Singh
(1)
As you can see this version is much quicker and runs in worst case in O(). Hope this run down of the dynamic version of LCS was helpful.
Sources:
I Feel All Sorts of Ways About Programming 