LDK算法python

LDK算法是一种用于求解最长公共子序列（Longest Common Subsequence，LCS）的动态规划算法。下面是一个简单的Python实现：

def ldk_algorithm(s1, s2):
    """
    LDK算法求解最长公共子序列
    :param s1: 字符串1
    :param s2: 字符串2
    :return: 最长公共子序列
    """
    m = len(s1)
    n = len(s2)
    # 初始化dp数组
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # 递推求解dp数组
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    # 回溯求解最长公共子序列
    lcs = ""
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            lcs = s1[i - 1] + lcs
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return lcs

其中，`s1`和`s2`分别是两个待求解最长公共子序列的字符串。函数返回的是这两个字符串的最长公共子序列。