def longest_common_subsequence_dp(s1, s2):
    """Longest common subsequence by dynamic programming.

    Time complexity: O(n1*n2).
    Space complexity: O(n1*n2).
    """
    n1, n2 = len(s1), len(s2)

    M = [[0] * (n2 + 1) for _ in range(n1 + 1)]

    for r in range(1, n1 + 1):
        for c in range(1, n2 + 1):
            if s1[r - 1] == s2[c - 1]:
                # If the current chars are the same, LCS is the last LCS plus 1.
                M[r][c] = M[r - 1][c - 1] + 1
            else:
                # If not, LCS is the max of LCS's w/o current char of text1 or text2.
                M[r][c] = max(M[r - 1][c], M[r][c - 1])

    return M[-1][-1]