Expert · Dynamic programming · 216 of 264
Longest common subsequence
Find the length of the longest sequence of characters that appears in both texts in the same order (not necessarily next to each other). Texts have up to 600 characters.
Input: two lines. Output: the length.
Examples
Input
ABCBDAB BDCABA
Output
4
Input
abc def
Output
0
Input
python python
Output
6
One more test checks other inputs when you press Check.
Stuck? The idea behind dynamic programming
Break the problem into smaller ones that repeat, and keep each answer in a table so it is worked out only once.
Decide what one cell of the table means ("the best total using the first i items"), how it follows from earlier cells, and where it starts.
n = 10
ways = [0] * (n + 1)
ways[0] = 1
for i in range(1, n + 1):
ways[i] = ways[i - 1] + (ways[i - 2] if i >= 2 else 0)
print(ways[n]) # climbing 10 stairs, 1 or 2 at a timeWatch for: Fill the table in an order where every cell it needs is already filled.