最长公共 上升子序列

### 最长公共上升子序列 (LCIS) 的动态规划解法 #### 定义与背景 最长公共上升子序列（Longest Common Increasing Subsequence, LCIS）是指给定两个序列 $X$ 和 $Y$，找到一个既是最长的又是严格递增的子序列，这个子序列同时属于 $X$ 和 $Y$。这个问题可以被看作是 **最长公共子序列** （LCS）和 **最长上升子序列** （LIS）问题的一个组合。 对于两个输入序列 $X = \{x_1, x_2, ..., x_m\}$ 和 $Y = \{y_1, y_2, ..., y_n\}$，目标是找出它们之间的 LCIS[^4]。 --- #### 动态规划的状态定义 设 $dp[i][j]$ 表示以 $X_i$ 结尾并与 $Y_j$ 对应的最长公共上升子序列的长度，则状态转移方程如下： $$ dp[i][j] = \begin{cases} 0 & 如果 i=0 或 j=0 \\ max(dp[k][l]) + 1 & 如果 X[i]=Y[j], 并且 k<i,l<j,X[k]<X[i]\\ dp[i][j-1] & 否则 \end{cases} $$ 其中，如果当前字符相等 ($X[i]==Y[j]$)，我们需要进一步检查之前所有的可能匹配位置 $(k,l)$ 来确保它是递增的，并更新最大值。 --- #### 时间复杂度分析 上述方法的时间复杂度较高，因为每次都需要遍历之前的元素来验证是否构成递增关系。因此总时间复杂度为 $O(mn^2)$ 或更高取决于具体实现方式。为了优化此过程，可以通过记录前驱索引来减少重复计算，从而降低到更优的时间复杂度如 $O(nm)$。 以下是基于 Python 的一种高效实现版本: ```python def lcis(X, Y): m, n = len(X), len(Y) # 初始化 DP 数组以及用于追踪路径的 prev 数组 dp = [[0]*(n+1) for _ in range(m+1)] prev = [[None]*(n+1) for _ in range(m+1)] max_len = 0 pos = -1 for i in range(1,m+1): for j in range(1,n+1): if X[i-1] == Y[j-1]: temp_max = 0 for p in range(j): if Y[p-1] < Y[j-1] and dp[i-1][p] > temp_max: temp_max = dp[i-1][p] dp[i][j] = temp_max + 1 if dp[i][j] > max_len: max_len = dp[i][j] pos = j else: dp[i][j] = dp[i][j-1] result = [] while pos is not None: result.append(Y[pos-1]) next_pos = prev[m][pos] pos = next_pos return list(reversed(result)) # 测试数据 print(lcis([3,4,9,1],[5,3,8,9,10,2,1])) # 输出可能是 [3,9,1] ``` 注意这段代码中的 `prev` 跟踪数组是为了方便最后重建实际的 LCIS 序列。 --- #### 总结 通过动态规划的方法求解最长公共上升子序列问题时，关键是合理设计状态表示并有效利用历史信息完成最优决策。尽管基础版算法存在较高的时间开销，但借助额外存储结构能够显著提升效率至可接受范围之内。