动态规划法实验：优化字符串比对

"该实验是计算机学院算法分析与设计课程的一部分，旨在通过动态规划法解决两个长字符串的最优化比对问题。实验由曹霑懋老师指导，于2010~2011学年第二学期进行，针对计算机科学与技术专业09级嵌入式4班的学生。实验的主要任务是将两个字符串S1和S2放置在二维矩阵中，以最大化相同字符的匹配数量。计分规则基于字符匹配、不匹配和空格的情况。实验要求使用C++编程语言，在VC6.0集成开发环境中实现动态规划算法并结合回溯法找到最长子序列。实验步骤包括明确目标、编写程序、运行并分析结果。提供的程序清单展示了动态规划算法的部分代码，用于计算字符串的匹配得分。" 实验详细解读： 1. **动态规划法**：动态规划是一种解决复杂问题的有效方法，通常用于寻找最优解。在这个实验中，动态规划被用来找到两个字符串S1和S2的最长公共子序列。这是一个典型的二维状态转移问题，通过构建一个矩阵a[i][j]来存储S1的前i个字符和S2的前j个字符的最长公共子序列的长度。 2. **初始化**：在动态规划算法的开始，矩阵a的边界条件被初始化。对于a[i][0]和a[0][j]，它们的值设置为-2 * i和-2 * j，这表示没有匹配的字符，因为一个空字符串与任何长度为i或j的字符串的最长公共子序列长度为0，加上负的惩罚分数。 3. **状态转移方程**：对于矩阵中的每个元素a[i][j]，如果s1[i-1]等于s2[j-1]，则匹配得分是5，表示找到了一个匹配的字符；如果不相等，则得分是-1，表示不匹配。这个过程反映了动态规划的核心思想，即通过比较当前字符和之前的最佳状态来决定当前状态的得分。 4. **回溯法**：在动态规划算法找到最长子序列的长度后，回溯法用于找出具体的最长子序列。通过跟踪得分最高的路径，回溯到原始字符串，可以得到匹配的字符序列。 5. **实验环境**：实验在PC机上进行，使用C++编程语言和VC6.0作为开发环境。这种环境支持编译和调试C++代码，以实现动态规划算法和回溯法的逻辑。 6. **实验结论**：通过运行程序并分析结果，学生可以深入理解动态规划法如何解决实际问题，以及如何利用回溯法找到最优解的具体路径。这有助于增强对动态规划法的理解和应用能力。 这个实验是一个很好的实践平台，让学生能够亲手实现并体验动态规划法的强大之处，同时加深了对这一重要算法的理解。