← All Exercises
Python LCS Dynamic Programming
advancedpython
Background
The LCS problem is fundamental in diff tools, DNA sequence alignment, and version control systems.
Problem
Write a function that takes two strings and returns the length of their longest common subsequence using DP.
Input
Two strings to compare.
Output
The length of the longest common subsequence.
Sample tests
Sample 1
Input: "ABCBDAB", "BDCAB"
Expected: 4
Your solution
Learning objective
Learn 2D dynamic programming, the LCS recurrence relation, and table filling.