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

"这篇资源主要讨论了动态规划在解决子序列问题中的应用，特别是最长公共子序列（LCS）问题。作者提到了动态规划的两个关键特性：最优子结构和重叠子问题，并通过代码示例展示了如何进行空间优化。此外，还提供了两个练习题目，一个是HDU1159，另一个是PKU1936，提示解题者这两道题都可以通过理解LCS来快速解决。" 动态规划是一种解决复杂问题的有效方法，它通过将大问题分解为小问题并存储中间结果来避免重复计算，从而提高效率。在这个资源中，重点讲解的是动态规划在处理子序列问题中的应用，尤其是最长公共子序列（LCS）问题。 LCS问题是寻找两个序列中的最长子序列，这个子序列不需要连续，但必须在原序列中都存在。对于两个序列x和y，定义c[i,j]为x的前i个元素和y的前j个元素的LCS长度，那么c[m,n]就是x和y的LCS长度。解决这个问题的关键在于识别最优子结构和重叠子问题。 1. **最优子结构**：LCS问题具有最优子结构，即一个序列的LCS可以通过其子序列的LCS来确定。如果x[i] = y[j]，那么LCS可以增加1；否则，LCS可能是不包含x[i]或y[j]的两个子序列的LCS中的较长者。 2. **重叠子问题**：动态规划的优势在于它可以解决具有大量重叠子问题的问题。在LCS问题中，计算任意位置的c[i,j]都需要用到之前计算的结果，如c[i-1,j]、c[i,j-1]等，这就是重叠子问题。 3. **空间优化**：原始的动态规划解决方案可能会使用二维数组，导致空间复杂度为O(m*n)，其中m和n分别为序列的长度。通过自底向上的递推，可以仅保留相邻两行，将空间复杂度降低到O(min{m,n})。进一步地，可以只保留一行，通过临时变量x保存上一行的值。 4. **初始化问题**：动态规划的初始化是至关重要的，确保对边界条件的正确处理，例如，当i或j为0时，LCS的长度应为0。 5. **练习题目**：资源中给出了两个题目，一个是HDU1159，另一个是PKU1936，都是基于LCS的。作者提示，理解LCS的本质可以帮助快速解决这些题目。 通过理解和掌握这些知识点，读者可以有效地解决与LCS相关的问题，并且能够应用动态规划的原理到其他类似的子序列问题中。