运用动态规划法算法解决最长公共子序列问题实验报告，包括设计分析、算法描述与程序、测试分析与总结

设计分析：

最长公共子序列问题（Longest Common Subsequence，LCS）是一个经典的计算机科学问题，其目标是找到两个序列中最长的公共子序列。例如，对于序列 S1 = "ABCDGH" 和序列 S2 = "AEDFHR"，它们的最长公共子序列为 "ADH"。该问题可以用动态规划法求解。

算法描述：

我们可以定义一个二维数组 dp，其中 dp[i][j] 表示序列 S1 中前 i 个字符和序列 S2 中前 j 个字符的最长公共子序列的长度。然后，我们可以通过以下方式递推地计算 dp 数组：

当 i=0 或 j=0 时，dp[i][j] = 0。

当 S1[i-1] = S2[j-1] 时，dp[i][j] = dp[i-1][j-1] + 1。

当 S1[i-1] != S2[j-1] 时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

最后，dp[m][n] 就是序列 S1 和序列 S2 的最长公共子序列的长度。

程序：

下面是一个使用 Python 编写的实现代码：

def longest_common_subsequence(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    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])
    return dp[m][n]

测试分析与总结：

我们可以使用一些测试数据来验证上述算法的正确性，例如：

s1 = "ABCDGH"
s2 = "AEDFHR"
最长公共子序列为 "ADH"，其长度为 3。

s1 = "AGGTAB"
s2 = "GXTXAYB"
最长公共子序列为 "GTAB"，其长度为 4。

通过测试数据的验证，我们可以看到上述算法的正确性。另外，通过对算法的时间复杂度分析，我们可以得出该算法的时间复杂度为 O(mn)，其中 m 和 n 分别是两个序列的长度。因此，我们可以得出结论：动态规划法是求解最长公共子序列问题的有效算法。