动态规划解析：自底向上解子序列问题

"自底向上递推-dp之子序列" 在动态规划领域，子序列问题是常见的算法问题，特别是最长公共子序列（Longest Common Subsequence, LCS）和最长上升子序列（Longest Increasing Subsequence, LIS）。这些问题是通过自底向上的递推方法来解决的，这种方法可以有效地避免重复计算，提高效率。 1. **最长公共子序列 (LCS)**: - LCS 是两个字符串 x 和 y 的子序列，但不需要连续，且长度最长。定义 c[i, j] 为 x[1..i] 和 y[1..j] 的 LCS 长度。 - 递推公式：如果 x[i] = y[j]，那么 c[i, j] = c[i-1, j-1] + 1；否则，c[i, j] = max(c[i-1, j], c[i, j-1])。 - 自底向上递推时，按照 i 和 j 的递增顺序计算，只需要存储相邻两行的数据，空间复杂度为 O(min{m, n})，其中 m 和 n 分别是两个字符串的长度。 - 初始化问题：通常，边界条件为 c[0, j] = 0 和 c[i, 0] = 0，表示空串与任意字符串的LCS长度为0。 2. **最长上升子序列 (LIS)**: - LIS 是一个序列中的一个子序列，其元素是严格递增的，且长度最长。对于一个数组，可以找到这样的子序列。 - 通常使用二分查找和单调栈或队列来优化求解，时间复杂度可以达到 O(n log n)。 - 自底向上递推时，对于每个元素，找到之前所有元素中最大的一个，使得当前元素大于它，然后更新这个最大值，从而得到每个位置的LIS长度。 3. **动态规划的关键点**： - **最优子结构**：问题的最优解可以通过其子问题的最优解组合得出。 - **重叠子问题**：问题的解包含大量重复的子问题，这是动态规划能发挥作用的关键。 4. **记忆化 (Memoization)**: - 为了避免重复计算，可以使用记忆化技术存储已经计算过的子问题结果，从而提高效率。 - 在自底向上递推过程中，记忆化通常是自动实现的，因为每个状态只计算一次。 5. **代码示例**： - 代码中使用了二维数组 dp 来存储状态，对于 LCS 问题，dp[i][j] 表示 x[1..i] 和 y[1..j] 的 LCS 长度。 - 在 PKU1936 这个题目中，虽然没有给出完整的代码，但可以看到使用了动态规划的思路，定义了一个二维数组 dp 并进行了初始化。 6. **练习题推荐**： - HDU1159 和 PKU1936 都是关于 LCS 的问题，适合用来练习动态规划和LCS的解题技巧。 动态规划的子序列问题通过自底向上递推的方法可以高效地求解，同时注意问题的最优子结构和重叠子问题特性，以及初始化和空间优化。通过实践和练习，可以更好地理解和掌握这些概念。