最长公共递增子序列 题目描述 给定两个整数数组 nums1 和 nums2 ，请找出它们的最长公共子序列，且该子序列必须是严格递增的。返回这个最长公共递增子序列的长度。 例如： nums1 = [1,3,5,4,7] nums2 = [1,2,3,4,5,6,7] 最长公共递增子序列是 [1,3,5,7] 或 [1,3,4,7] ，长度均为 4。 解题过程 1. 问题分析 本题结合了“最长公共子序列（LCS）”和“最长递增子序列（LIS）”的特点，要求子序列同时满足： 是 nums1 和 nums2 的公共子序列； 严格递增。 直接套用 LCS 的二维动态规划方法无法保证递增性，需要扩展状态定义。 2. 状态定义 定义 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共递增子序列的长度。 注意：这里要求子序列必须以 nums1[i-1] 和 nums2[j-1] 结尾，且这两个元素相等。 但这样定义无法直接递推，因为当 nums1[i-1] != nums2[j-1] 时， dp[i][j] 无意义（设为 0）。我们需要另一个辅助状态来记录递增关系。 改进状态定义 ： 设 dp[i][j] 表示考虑 nums1 的前 i 个元素和 nums2 的前 j 个元素时，以 nums2[j-1] 结尾的最长公共递增子序列的长度。 这样，当 nums1[i-1] == nums2[j-1] 时，我们可以尝试将当前元素接在之前的公共递增子序列后面。 3. 状态转移方程 如果 nums1[i-1] != nums2[j-1] ： 当前元素不能同时作为结尾，因此 dp[i][j] = dp[i-1][j] ？不对，因为 dp[i][j] 是以 nums2[j-1] 结尾的，如果不等，则 dp[i][j] 应该继承不考虑 nums1[i-1] 时的值，但保留以 nums2[j-1] 结尾的可能性。实际上，更合理的做法是： dp[i][j] = dp[i-1][j] （忽略 nums1[i-1] ，因为当前无法匹配）。 如果 nums1[i-1] == nums2[j-1] ： 我们需要找一个在 nums2 中位置在 j 之前且值小于 nums2[j-1] 的元素 nums2[k] （k < j），使得 nums1 中也有对应匹配，从而形成递增序列。 因此： dp[i][j] = max{ dp[i-1][k] + 1 } ，其中 k < j 且 nums2[k-1] < nums2[j-1] 。 同时，至少长度为 1（只取当前元素）。 4. 优化递推 直接枚举 k 会导致 O(n³) 复杂度。我们可以优化： 在遍历 j 时，维护一个变量 maxLen ，记录对于当前 i，所有满足 nums2[k-1] < nums1[i-1] （即 nums2[k-1] < nums2[j-1] ，因为此时相等）的 dp[i-1][k] 的最大值。 这样，当 nums1[i-1] == nums2[j-1] 时，直接 dp[i][j] = maxLen + 1 。 5. 算法步骤 初始化一个二维数组 dp ，大小为 (len1+1) x (len2+1) ，初始为 0。 遍历 i 从 1 到 len1： 初始化 maxLen = 0 。 遍历 j 从 1 到 len2： 如果 nums1[i-1] == nums2[j-1] ： dp[i][j] = maxLen + 1 。 否则： dp[i][j] = dp[i-1][j] 。 如果 nums2[j-1] < nums1[i-1] ： 更新 maxLen = max(maxLen, dp[i-1][j]) 。 最终答案取 dp[len1][j] 中的最大值（j 从 1 到 len2）。 6. 示例演算 nums1 = [1,3,5,4,7] nums2 = [1,2,3,4,5,6,7] 初始化 dp 为 0。 i=1（nums1[ 0 ]=1）： j=1（nums2[ 0]=1）：相等，maxLen=0 → dp[ 1][ 1 ]=1。 j=2（2 <1？不更新 maxLen）… i=2（nums1[ 1 ]=3）： maxLen=0 j=1（1<3）：maxLen=max(0,dp[ 1][ 1 ]=1)=1 j=2（2<3）：maxLen=max(1,dp[ 1][ 2 ]=0)=1 j=3（3==3）：dp[ 2][ 3 ]=1+1=2 继续遍历，最终最大值为 4。 7. 复杂度分析 时间复杂度：O(len1 × len2) 空间复杂度：O(len1 × len2)，可优化到 O(len2)