南华大学动态规划实验：最长公共子串与美食策略

南华大学计算机学院的2022-2023学年度第二学期算法分析与设计实验重点关注了动态规划这一核心概念。实验分为以下几个部分： 1. 实验目的：实验的主要目标是让学生深入理解动态规划算法的思想，并将其运用到实际问题中，如找出两个给定字符串的最长公共子串长度和美食家大宝在小吃街上选择最满意食物路径的问题。通过这两个实例，学生将学习如何将复杂问题分解为可管理的子问题，以便找到全局最优解。 2. 实验环境：学生在实验中使用的平台包括Windows 10操作系统，以及集成开发环境如IntelliJ IDEA Community Edition 2021.1 x64版本，以及Visual Studio 2019和Visual Studio Code。这些工具为编程和代码实现提供了支持。 3. 实验内容： - **最长公共子串长度**：通过编写程序找出两个字符串中最长的公共子串，例如输入"1AB2345CD"和"12345EF"，输出4，展示了动态规划在字符串处理中的应用。 - **美食家大宝**：这个问题模拟了一个实际场景，涉及对美味度进行排序和决策，目的是寻找最多数量的"爽"的体验，即美味度连续且满足一定条件的食物组合。这需要学生用动态规划的方法确定最优化的路径。 4. 实验设计（问题解决方案）：这部分可能包括递推公式、状态转移方程的构建，以及如何利用先前计算过的子问题结果来避免重复计算，这是动态规划的关键要素。学生需要设计一个算法，比如使用一个二维数组或自底向上的方法，存储每个子问题的最优解。 5. 程序及结果：实验过程中，学生需编写并运行代码，记录关键步骤和结果，这有助于加深对动态规划的理解。提供的样例输入和输出可以帮助他们检验代码的正确性。 6. 实验总结：实验总结部分强调了动态规划的价值，它是一种解决复杂问题的有效策略，不仅在计算机科学中，还在其他领域如管理学、经济学等领域发挥着重要作用。学生通过实践了解到，动态规划的核心在于识别子问题之间的依赖关系，以及如何利用已知最优解来求解新的问题。 通过这个实验，学生不仅能掌握动态规划的基本原理，还能提升算法设计和解决实际问题的能力。