线性动态规划：最长公共递增子序列（LCIS）

字数 2012 2025-11-29 15:08:18

线性动态规划：最长公共递增子序列（LCIS）

我将为你讲解最长公共递增子序列（Longest Common Increasing Subsequence, LCIS）问题。这个问题结合了最长公共子序列（LCS）和最长递增子序列（LIS）的特点，要求找出两个序列中公共的、且严格递增的子序列中最长的一个。

问题描述

给定两个整数序列 A（长度为 n）和 B（长度为 m），找出最长的序列 C，使得 C 既是 A 的子序列，也是 B 的子序列，并且 C 中的元素严格递增。输出这个最长公共递增子序列的长度。

示例：

输入：A = [1, 3, 5, 2, 4], B = [3, 1, 2, 5, 4]
输出：3
解释：最长公共递增子序列可以是 [1, 2, 4] 或 [3, 4] 等，但最长长度为 3。

解题思路

我们可以通过动态规划来解决这个问题。关键在于设计一个状态表示，能够同时捕捉“公共”和“递增”两个约束条件。

步骤 1：定义状态

设 dp[i][j] 表示以 B[j] 结尾的、且考虑 A 的前 i 个元素时的最长公共递增子序列的长度。

为什么这样定义？

以 B[j] 结尾：这样我们可以利用递增的性质，在匹配到 A[i] 和 B[j] 时，检查之前的公共递增子序列是否可以扩展。
考虑 A 的前 i 个元素：确保子序列是 A 和 B 的公共子序列。

步骤 2：状态转移方程

我们需要考虑两种情况：

如果 A[i] != B[j]：那么 B[j] 不能作为公共子序列的结尾，所以 dp[i][j] = dp[i-1][j]（即不考虑 A[i] 时的结果）。
如果 A[i] == B[j]：说明我们找到了一个公共元素，此时需要找到一个以小于 B[j] 的值结尾的公共递增子序列，来扩展成以 B[j] 结尾的更长序列。因此：
- 初始化 dp[i][j] = 1（至少可以单独以 B[j] 作为一个子序列）。
- 遍历 B 中所有小于 B[j] 的位置 k（即 0 <= k < j 且 B[k] < B[j]），并更新：
```
dp[i][j] = max(dp[i][j], dp[i-1][k] + 1)
```
- 注意：这里使用 dp[i-1][k] 是因为 A[i] 已经被用于匹配 B[j]，所以之前的状态应基于 A 的前 i-1 个元素。

步骤 3：初始化

对于任何 i 或 j，如果 A[i] 或 B[j] 不匹配，初始值可以设为 0 或继承前一个状态。通常我们初始化一个二维数组 dp，大小为 (n+1) x (m+1)，并将第一行和第一列初始化为 0，以处理边界情况。

步骤 4：计算顺序

外层循环遍历 i 从 1 到 n（A 的每个元素）。
内层循环遍历 j 从 1 到 m（B 的每个元素）。
在内层循环中，当 A[i] == B[j] 时，需要再内嵌一个循环遍历 k 从 0 到 j-1，检查所有可能的 B[k] < B[j]。

步骤 5：结果提取

最终结果是所有 dp[i][j] 中的最大值，因为最长公共递增子序列可能以任何 B[j] 结尾。

优化：降低时间复杂度

上述直接方法的时间复杂度是 O(n·m²)，因为有三层循环。我们可以优化内层循环：

在内层循环 j 时，维护一个变量 maxLen，记录对于当前 i，所有满足 B[k] < B[j] 的 dp[i-1][k] 的最大值。
这样，当 A[i] == B[j] 时，直接令 dp[i][j] = maxLen + 1，避免了内嵌循环。
维护 maxLen 的方法：在遍历 j 时，如果 B[j] < A[i]（注意这里比较的是 A[i]，因为我们在找小于当前匹配值的元素），则更新 maxLen = max(maxLen, dp[i-1][j])。

优化后的时间复杂度为 O(n·m)。

示例演示

以 A = [1, 3, 5, 2, 4], B = [3, 1, 2, 5, 4] 为例，使用优化后的方法计算 dp 表（简化表示）：

初始化 dp 为全 0。
遍历 i=1（A[0]=1）：
- j=1：B[0]=3 != 1，dp[1][1]=0；更新 maxLen：因为 3>1，不更新。
- j=2：B[1]=1 == 1，dp[1][2] = maxLen + 1 = 0+1=1。
- 其余 j 类似。
继续处理所有 i，最终找到最大值为 3。

总结

LCIS 问题通过动态规划状态巧妙结合了公共性和递增性。优化后的算法高效且易于实现，是线性动态规划中一个经典的综合性问题。

线性动态规划：最长公共递增子序列（LCIS）我将为你讲解最长公共递增子序列（Longest Common Increasing Subsequence, LCIS）问题。这个问题结合了最长公共子序列（LCS）和最长递增子序列（LIS）的特点，要求找出两个序列中公共的、且严格递增的子序列中最长的一个。问题描述给定两个整数序列 A （长度为 n ）和 B （长度为 m ），找出最长的序列 C ，使得 C 既是 A 的子序列，也是 B 的子序列，并且 C 中的元素严格递增。输出这个最长公共递增子序列的长度。示例：输入： A = [1, 3, 5, 2, 4] , B = [3, 1, 2, 5, 4] 输出： 3 解释：最长公共递增子序列可以是 [1, 2, 4] 或 [3, 4] 等，但最长长度为 3。解题思路我们可以通过动态规划来解决这个问题。关键在于设计一个状态表示，能够同时捕捉“公共”和“递增”两个约束条件。步骤 1：定义状态设 dp[i][j] 表示以 B[j] 结尾的、且考虑 A 的前 i 个元素时的最长公共递增子序列的长度。为什么这样定义？以 B[j] 结尾：这样我们可以利用递增的性质，在匹配到 A[i] 和 B[j] 时，检查之前的公共递增子序列是否可以扩展。考虑 A 的前 i 个元素：确保子序列是 A 和 B 的公共子序列。步骤 2：状态转移方程我们需要考虑两种情况：如果 A[i] != B[j] ：那么 B[j] 不能作为公共子序列的结尾，所以 dp[i][j] = dp[i-1][j] （即不考虑 A[i] 时的结果）。如果 A[i] == B[j] ：说明我们找到了一个公共元素，此时需要找到一个以小于 B[j] 的值结尾的公共递增子序列，来扩展成以 B[j] 结尾的更长序列。因此：初始化 dp[i][j] = 1 （至少可以单独以 B[j] 作为一个子序列）。遍历 B 中所有小于 B[j] 的位置 k （即 0 <= k < j 且 B[k] < B[j] ），并更新：注意：这里使用 dp[i-1][k] 是因为 A[i] 已经被用于匹配 B[j] ，所以之前的状态应基于 A 的前 i-1 个元素。步骤 3：初始化对于任何 i 或 j ，如果 A[i] 或 B[j] 不匹配，初始值可以设为 0 或继承前一个状态。通常我们初始化一个二维数组 dp ，大小为 (n+1) x (m+1) ，并将第一行和第一列初始化为 0，以处理边界情况。步骤 4：计算顺序外层循环遍历 i 从 1 到 n （ A 的每个元素）。内层循环遍历 j 从 1 到 m （ B 的每个元素）。在内层循环中，当 A[i] == B[j] 时，需要再内嵌一个循环遍历 k 从 0 到 j-1 ，检查所有可能的 B[k] < B[j] 。步骤 5：结果提取最终结果是所有 dp[i][j] 中的最大值，因为最长公共递增子序列可能以任何 B[j] 结尾。优化：降低时间复杂度上述直接方法的时间复杂度是 O(n·m²)，因为有三层循环。我们可以优化内层循环：在内层循环 j 时，维护一个变量 maxLen ，记录对于当前 i ，所有满足 B[k] < B[j] 的 dp[i-1][k] 的最大值。这样，当 A[i] == B[j] 时，直接令 dp[i][j] = maxLen + 1 ，避免了内嵌循环。维护 maxLen 的方法：在遍历 j 时，如果 B[j] < A[i] （注意这里比较的是 A[i] ，因为我们在找小于当前匹配值的元素），则更新 maxLen = max(maxLen, dp[i-1][j]) 。优化后的时间复杂度为 O(n·m)。示例演示以 A = [1, 3, 5, 2, 4] , B = [3, 1, 2, 5, 4] 为例，使用优化后的方法计算 dp 表（简化表示）：初始化 dp 为全 0。遍历 i=1 （ A[0]=1 ）： j=1 ： B[0]=3 != 1， dp[1][1]=0 ；更新 maxLen ：因为 3>1 ，不更新。 j=2 ： B[1]=1 == 1， dp[1][2] = maxLen + 1 = 0+1=1 。其余 j 类似。继续处理所有 i ，最终找到最大值为 3。总结 LCIS 问题通过动态规划状态巧妙结合了公共性和递增性。优化后的算法高效且易于实现，是线性动态规划中一个经典的综合性问题。