北大《算法设计与分析》实习报告-动态规划专题

"北大POJ试题部分 - C++编程 - 动态规划算法" 这篇资源主要涉及的是北京大学一门名为《算法设计与分析》的课程中的实习报告要求和一个具体的动态规划问题——寻找两个字符序列的最长公共子序列。课程对学生的作业提交有明确的规定，包括命名格式、提交方式、评分标准以及学术诚信的要求。此外，还强调了作业的及时性和独立完成的重要性。 在实习题目部分，提到了一个动态规划的应用实例——题目1458。动态规划是一种用于求解最优化问题的方法，通过构建子问题并存储中间结果来避免重复计算，从而提高效率。在这个问题中，目标是找到两个字符序列的最长公共子序列（LCS）。LCS是指在不改变子序列顺序的情况下，两个序列共有的最长子序列。 动态规划的解决方案通常涉及一个二维数组，其中每个元素表示对应位置的两个字符序列的LCS长度。在给定的源代码中，数组`c[m][n]`用于存储这两个序列的LCS长度，`m`和`n`分别代表两个字符序列的长度。程序首先读入两个序列`a`和`b`，然后通过循环计算`c`数组的所有元素。算法的核心思路基于以下三个条件： 1. 如果序列末尾的字符相同，那么最长公共子序列会在末尾增加这个字符。 2. 如果末尾字符不同，但去掉其中一个序列的末尾字符后仍有公共子序列，选择保留LCS较长的那个。 3. 如果末尾字符都不同，且在各自的序列中前一位置也无公共子序列，那么最长公共子序列就是分别与两个序列的前一位置对应的LCS。 效率分析表明，这个算法的时间复杂度为O(m * n)，其中m和n分别是两个输入序列的长度。这表明算法的效率较高，因为它只遍历一次二维数组。 在实际编程中，为了更好地理解算法和展示过程，推荐使用图形化工具如Visio绘制状态转移图，以直观地展示动态规划的过程。 这个实习任务旨在帮助学生掌握动态规划的基本原理，并能运用到实际问题中，通过编写C++代码解决字符序列的最长公共子序列问题。同时，它也强调了课程考核的全面性，包括笔试、平时作业和课堂表现，以及对学术诚信的重视。