动态规划解析：最长上升子序列与最长公共子序列

"该资源主要讲述了动态规划在解决子序列问题中的应用，特别是最长公共子序列（LCS）和最长上升子序列（LIS）。" 在动态规划领域，子序列问题是一个常见的主题。动态规划是一种通过将复杂问题分解为更小的子问题来求解的方法，它利用已解决的子问题的最优解来构建原问题的最优解。本文主要关注两个子序列问题：最长公共子序列和最长上升子序列。 一、最长公共子序列（LCS） LCS问题是寻找两个给定序列的最长子序列，这个子序列不必连续，但必须保持原序。解决这个问题的关键在于最优子结构和重叠子问题。 1. 最优子结构：问题的最优解可以通过其子问题的最优解组合得出。在LCS问题中，如果两个序列的某个位置的字符相同，那么最优解包括这个字符；如果不同，则可以从不包含这个字符的两个子序列中选择较长的一个。 2. 重叠子问题：LCS问题中有许多相同的子问题被重复计算，这使得动态规划成为理想的解决方案。通过记忆化技术，我们可以存储已经计算过的子问题结果，避免重复计算。 3. 程序实现：通常使用二维数组`dp[i][j]`表示两个序列到当前位置的LCS长度。递推公式是`dp[i][j] = max(dp[i-1][j-1] + (x[i] == y[j]), max(dp[i-1][j], dp[i][j-1]))`。通过自底向上的方式计算，可以使用滚动数组减少空间复杂度。 4. 空间优化：当只关心最终结果时，可以使用滚动数组仅保留相邻两行，甚至仅保留一行，大大减少了空间需求。 5. 初始化：在初始化`dp`数组时，需要正确处理边界情况，例如当一个序列为空时，LCS长度为0。 二、最长上升子序列（LIS） LIS问题寻找一个序列的最长子序列，使得子序列中的元素严格递增。它的解决方法与LCS类似，但不考虑字符匹配，而是关注元素的大小关系。 1. 解题分析：LIS问题同样具备最优子结构和重叠子问题特性，可以通过动态规划解决。一般使用单调栈或二分查找优化的动态规划方法，时间复杂度可达到O(n log n)。 2. 示例题目：文中给出了两个LCS相关的编程题目，分别是HDU1159和PKU1936，这两个题目都可以通过应用LCS的基本思想来解决。 3. 代码示例：给出的代码片段是C++实现的LCS解法，使用了二维数组`dp`来存储中间结果，并定义了辅助函数`max`来比较两个整数。 总结，动态规划在解决子序列问题时，通过最优子结构和重叠子问题的特性，能够有效地找到序列的最长公共子序列和最长上升子序列。在实际编程中，要注意空间优化和初始化策略，以提高算法的效率和正确性。