动态规划算法实现——最长公共子序列问题

"浙江工业大学算法实验2 动态规划算法实现.docx" 在这个实验中，学生将学习和应用动态规划算法来解决实际问题。动态规划是一种优化技术，它通过将复杂问题分解为更小的子问题来求解，通常用于处理具有重叠子问题和最优子结构的场景。在实验中，主要关注的是找到两个字符串的最长公共子序列（Longest Common Subsequence, LCS）。 最长公共子序列是两个字符串中没有重新排序的最长子串，这两个子串可能不相邻，但它们在各自的字符串中都存在。在实验中，给出了两个示例字符串，即 "ABCBDAB" 和 "BDCABA"，以及 "zhejianguniversityoftechnology" 和 "zhejianguniversitycitycollege"，目的是让学生编写代码找出这些字符串的LCS。 实验代码中，`LCSLength` 函数是核心，它接受两个字符串的长度 `m` 和 `n`，以及两个二维整数数组 `c` 和 `b`。数组 `c` 用于存储子问题的解，而 `b` 用于记录解的来源。函数首先初始化 `c` 数组的边界条件，然后通过两层循环计算所有可能的子问题。在内层循环中，如果当前字符匹配，那么公共子序列的长度会增加1；否则，会选择之前已知的较大值来更新当前位置的值。`b` 数组的值1、2、3分别表示子问题的解来源于上一行、左列或对角线上的元素。 `LCS` 函数则根据 `b` 数组构造出最长公共子序列。它是一个递归函数，根据 `b` 数组中的标记选择合适的路径回溯，输出最长公共子序列。 在主函数 `main` 中，用户被要求输入两个字符串，然后调用 `LCSLength` 计算长度，并用 `LCS` 构造并打印出最长公共子序列。 这个实验不仅涵盖了动态规划的基本概念，还强调了如何将理论知识转化为实际代码，对于理解动态规划的原理和应用有极大的帮助。通过这样的练习，学生可以增强解决问题的能力，同时提高编程技巧。