Challenge 1

Compute Fibonacci with DP and print it.

Challenge 1: LCS

In this challenge you will solve the longest common subsequence (LCS) problem with dynamic programming. You will find the LCS of two strings.

Strings are s1 = 'AGGTAB' and s2 = 'GXTXAYB'. The LCS length is 4. Build a DP table to produce this result.

Exercise lcs_length function

Write lcs_length(s1, s2). Build a DP table, return the LCS length. Print 4 with print(lcs_length('AGGTAB', 'GXTXAYB')).

Show example solution

def lcs_length(s1, s2):
    # Find LCS length with DP
    dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
    for i in range(1, len(s1) + 1):
        for j in range(1, len(s2) + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[len(s1)][len(s2)]
print(lcs_length('AGGTAB', 'GXTXAYB'))

Test yourself

How many strings does LCS use?
- Two strings
- Three strings
- One string
- Empty string
Show answer

Two strings — LCS compares two strings.

DP recurrence

if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][____-1] + 1

Show answer

if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1

Challenge 1: match the terms

s1

AGGTAB
s2

GXTXAYB
LCS

GTAB
length

4

Next lesson: Challenge 2

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies