实验3-动态规划算法1

实验3主要探讨了动态规划算法在解决实际问题中的应用，特别是针对两个核心问题：最长公共子序列（LCS）问题和最大子段和问题。动态规划是一种强大的算法设计策略，它通过将复杂问题分解为更小的子问题来求解，并存储子问题的解以避免重复计算。 我们关注最长公共子序列问题。最长公共子序列是指两个或多个序列中，没有改变顺序的最长子序列。在这个实验中，我们有两个字符串X和Y，分别代表"ABCBDAB"和"BDCABA"，以及另外两个更长的字符串，用于测试更复杂的情况。不记录b方案是指在计算LCS时不保留中间过程的b值，即不保存所有可能的LCS，而是只保留当前最优解。实现这个算法的关键是构建一个二维数组，其中每个元素表示对应子串的LCS长度。通过比较字符并更新数组，我们可以找到两个字符串的LCS。 接着，我们讨论最大子段和问题，这是一个经典的动态规划问题。给定一个数组，目标是找到一个连续子数组，其元素之和最大。实验中给出了两个数据集：(-2, 11, -4, 13, -5, -2) 和一段过去三百年太阳黑子数的历史数据。这个问题可以通过Kadane's algorithm来解决，该算法通过遍历数组一次，分别记录当前子数组的最大和以及全局最大和，从而找到最大子段和。与三重循环和分治法相比，动态规划在这类问题上的优势在于效率和简洁性，它避免了冗余计算，提高了时间复杂度。 对于三重循环方法，它通常涉及到三个嵌套循环，对于每个元素，都要遍历所有可能的子数组起点和终点，效率较低。而分治法在解决这类问题时可能不太适用，因为它通常适用于可以递归地拆分为相同或相似子问题的问题，而最大子段和问题并不具备这样的特性。 实验报告应该包括以下部分：1）程序应能接收文本文件或键盘输入的数据。2）提交的Word版本实验报告应包含源代码和实验结果的屏幕截图。此外，报告还应包含对动态规划算法的理解，以及在解决问题过程中遇到的挑战和收获。 通过这个实验，学生不仅能够深入理解动态规划的基本思想，还能掌握如何在实际问题中应用这些概念。同时，他们还将学会如何评估不同算法的性能，并且通过编写和调试代码，增强问题解决能力和编程技巧。这是一次对理论知识和实践能力的综合训练。