动态规划实验报告：矩阵链乘与最长公共子序列

"PB16110173-徐煜森-project21" 这篇实验报告主要涉及了两个动态规划问题的实现：矩阵链乘问题和最长公共子序列问题。实验者徐煜森使用C++编程语言，在Windows 10环境下利用Visual Studio 2017开发工具进行，同时提供了方便在Linux环境下编译运行的Makefile。 1. **矩阵链乘问题**： - 实验要求：对于不同规模的矩阵链（n=5,10,20,30），生成n+1个随机整数表示矩阵的规模，并找到最优的乘法顺序，减少运算次数。 - 数据生成：使用`rand()%30+1`生成[1,30]区间内的数据，共31个数，代表矩阵的维度。 - 动态规划算法：算法与课堂讲解一致，使用二维数组`p`记录最小代价，一维数组`m`记录最优点，数组`s`记录最优路径。这里，实验者将矩阵的长度设为`length`，而在课本伪代码中通常使用`length-1`，这是因为实验者的实现中直接考虑了完整的长度值。 2. **最长公共子序列问题**： - 实验要求：在两组数据集（A组和B组，分别对应不同的序列长度）中，计算不同长度的两个随机生成字母序列的最长公共子序列，分析算法性能。 - 数据生成：A组序列长度为(15,10)到(15,60)，B组为(15,25)到(90,25)，元素取自26个大写字母。 - 动态规划算法：与课堂讲解的LCS算法相同，使用二维数组来存储子序列的长度，通过比较两个序列的对应字符来递归计算。 实验过程中，徐煜森记录了算法运行所需的时间并绘制了时间曲线，这有助于理解算法在不同规模问题上的时间复杂度表现。实验结果包括屏幕输出的运行时间和计算结果，所有数据均按照实验要求输出到文件。 通过这两个实验，可以学习到动态规划在解决实际问题中的应用，以及如何通过调整数据规模和算法实现来分析其性能。这对于理解和优化算法具有重要意义，也是计算机科学教育中的重要环节。