Challenge 1
- Algorithms course
- Advanced
- Lesson 53/56
- 4 min
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.
Practice lcs_length function
Write lcs_length(s1, s2). Build a DP table, return the LCS length. Print 4 with print(lcs_length('AGGTAB', 'GXTXAYB')).
Starter code
def lcs_length(s1, s2):
# Find LCS length with DPSample 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'))Expected output
4
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 How many strings does LCS use?
- Two strings Correct answer
- Three strings
- One string
- Empty string
Explanation: LCS compares two strings.
2 DP recurrence
Question
if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][____-1] + 1
Answer
if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1Explanation: j is right.
3 Challenge 1: match the terms
| Term | Meaning |
|---|---|
s1 |
AGGTAB |
s2 |
GXTXAYB |
LCS |
GTAB |
length |
4 |