def LCS(A, B):
    """
    Solver for LCS(Longest common subseqeunce problem), DP solution
    :param A: string A
    :param B: string B
    :return: the length of LCS
    """
    n = len(A)
    m = len(B)
    if m == 0 or n == 0:
        return -1
    c = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if A[i - 1] == B[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i][j - 1], c[i - 1][j])
    return c[-1][-1]