南京邮电大学动态规划法实验：最长公共子序列

"南京邮电大学的一份关于算法分析与设计的实验报告，重点探讨了动态规划法的应用，特别是最长公共子序列问题的解决。实验报告由计算机学院和软件学院的学生完成，指导教师提供指导，实验类型为验证性实验，时长2学时。报告中包含了一个使用备忘录方法实现的动态规划算法，用于避免子问题的重复求解。" 实验报告详述了动态规划法在解决实际问题中的应用，特别是在计算两个字符串的最长公共子序列（Longest Common Subsequence, LCS）时。动态规划是一种有效的问题解决策略，通过将大问题分解为更小的子问题，并存储子问题的解决方案，以避免重复计算。在这个实验中，学生们被要求改写现有的LCSLength()函数，采用备忘录方法优化，从而提高算法效率。 备忘录方法的核心在于记忆化搜索，它使用一个二维数组（如报告中的"c"和"s"数组）来存储已经计算过的子问题的结果。在LCSLength_Memo()函数中，这个二维数组被用来存储子问题的LCS长度，当需要再次计算相同的子问题时，可以直接从数组中查找结果，而不是重新计算。同时，为了实现递归求解，还定义了一个私有成员函数LCSLength_Memo(int i, int j)，该函数会递归地处理子问题。 报告中的代码示例展示了一个基于C++的实现，包含了类LCS的定义，其中包括了构造函数、析构函数以及与LCS计算相关的公共和私有成员函数。其中，LCSLength()函数是公有的，用于调用私有的递归函数LCSLength_Memo()，后者则是实际执行备忘录算法的地方。此外，CLCS()和CLCS(int i, int j)函数分别用于构造LCS，它们也是非递归的辅助函数。 这个实验旨在让学生深入理解动态规划法的概念，并能够熟练应用到实际编程中。通过解决最长公共子序列问题，学生可以学习如何设计和实现备忘录策略，这在处理复杂度较高的递归问题时非常有用，能够显著提升算法的运行效率。