Dynamic Programming — Longest Common Subsequence

Given two strings s1 and s2, return the length of their longest common subsequence (LCS).

A subsequence is formed by deleting some characters without changing the order.

Examples

• solve("abcde", "ace") → 3 ("ace")
• solve("abc", "abc") → 3
• solve("abc", "def") → 0

Constraints

• Use bottom-up 2-D DP table.
• 0 ≤ len(s1), len(s2) ≤ 1000.