hdu 1159 最长公共子序列

### HDU 1159 最长公共子序列 (LCS) 解题思路

#### 动态规划状态定义
对于两个字符串 `X` 和 `Y`，长度分别为 `n` 和 `m`。设 `dp[i][j]` 表示 `X[0...i-1]` 和 `Y[0...j-1]` 的最长公共子序列的长度。

当比较到第 `i` 个字符和第 `j` 个字符时：

- 如果 `X[i-1]==Y[j-1]`，那么这两个字符可以加入之前的 LCS 中，则有 `dp[i][j]=dp[i-1][j-1]+1`[^3]。

- 否则，如果 `X[i-1]!=Y[j-1]`，那么需要考虑两种情况中的最大值：即舍弃 `X[i-1]` 或者舍弃 `Y[j-1]`，因此取两者较大者作为新的 LCS 长度，即 `dp[i][j]=max(dp[i-1][j], dp[i][j-1])`。

时间复杂度为 O(n*m)，其中 n 是第一个字符串的长度而 m 是第二个字符串的长度。

#### 实现代码
以下是 Python 版本的具体实现方式：

def lcs_length(X, Y):
    # 初始化二维数组用于存储中间结果
    m = len(X)
    n = len(Y)
    
    # 创建(m+1)x(n+1)大小的表格来保存子问题的结果
    dp = [[0]*(n+1) for _ in range(m+1)]

    # 填充表项
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

# 测试数据输入部分可以根据具体题目调整
if __name__ == "__main__":
    while True:
        try:
            a = input().strip()
            b = input().strip()

            result = lcs_length(a,b)

            print(result)
            
        except EOFError:
            break

此程序会读入多组测试案例直到遇到文件结束符（EOF）。每组案例由两行组成，分别代表要计算其 LCS 的两个字符串。最后输出的是它们之间最长公共子序列的长度。