C++如何解决最长上升子序列和公共子序列问题

在算法和数据结构中，最长上升子序列（Longest Increasing Subsequence, LIS）和最长公共子序列（Longest Common Subsequence, LCS）是两个经典的问题。它们不仅在算法竞赛中经常出现，也在实际应用中有着广泛的应用场景。本文将详细介绍如何使用C++解决这两个问题，并提供相应的代码示例。

1. 最长上升子序列（LIS）

1.1 问题描述

给定一个整数序列，找到其中最长的严格递增子序列的长度。子序列不要求连续，但要求元素在原序列中的相对顺序不变。

例如，给定序列 [10, 9, 2, 5, 3, 7, 101, 18]，最长上升子序列是 [2, 3, 7, 101]，长度为4。

1.2 动态规划解法

动态规划是解决LIS问题的经典方法。我们定义一个数组 dp，其中 dp[i] 表示以第 i 个元素结尾的最长上升子序列的长度。状态转移方程如下：

dp[i] = max(dp[j]) + 1, 其中 0 <= j < i 且 nums[j] < nums[i]

最终的结果是 dp 数组中的最大值。

1.2.1 C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>

int lengthOfLIS(std::vector<int>& nums) {
    if (nums.empty()) return 0;
    
    std::vector<int> dp(nums.size(), 1);
    int maxLen = 1;
    
    for (int i = 1; i < nums.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
        maxLen = std::max(maxLen, dp[i]);
    }
    
    return maxLen;
}

int main() {
    std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    std::cout << "Length of LIS: " << lengthOfLIS(nums) << std::endl;
    return 0;
}

1.3 二分查找优化

上述动态规划解法的时间复杂度为 O(n^2)，对于较大的数据集来说效率较低。我们可以通过二分查找将时间复杂度优化到 O(n log n)。

1.3.1 C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>

int lengthOfLIS(std::vector<int>& nums) {
    std::vector<int> dp;
    
    for (int num : nums) {
        auto it = std::lower_bound(dp.begin(), dp.end(), num);
        if (it == dp.end()) {
            dp.push_back(num);
        } else {
            *it = num;
        }
    }
    
    return dp.size();
}

int main() {
    std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    std::cout << "Length of LIS: " << lengthOfLIS(nums) << std::endl;
    return 0;
}

2. 最长公共子序列（LCS）

2.1 问题描述

给定两个字符串 text1 和 text2，找到它们的最长公共子序列的长度。子序列要求元素在原字符串中的相对顺序不变，但不要求连续。

例如，给定 text1 = "abcde" 和 text2 = "ace"，最长公共子序列是 "ace"，长度为3。

2.2 动态规划解法

LCS问题同样可以使用动态规划来解决。我们定义一个二维数组 dp，其中 dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。状态转移方程如下：

if text1[i-1] == text2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

最终的结果是 dp[m][n]，其中 m 和 n 分别是 text1 和 text2 的长度。

2.2.1 C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>

int longestCommonSubsequence(std::string text1, std::string text2) {
    int m = text1.length();
    int n = text2.length();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (text1[i-1] == text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    return dp[m][n];
}

int main() {
    std::string text1 = "abcde";
    std::string text2 = "ace";
    std::cout << "Length of LCS: " << longestCommonSubsequence(text1, text2) << std::endl;
    return 0;
}

2.3 空间优化

上述动态规划解法使用了 O(m*n) 的空间复杂度。我们可以通过滚动数组的方式将空间复杂度优化到 O(n)。

2.3.1 C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>

int longestCommonSubsequence(std::string text1, std::string text2) {
    int m = text1.length();
    int n = text2.length();
    std::vector<int> dp(n + 1, 0);
    
    for (int i = 1; i <= m; ++i) {
        int prev = 0;
        for (int j = 1; j <= n; ++j) {
            int temp = dp[j];
            if (text1[i-1] == text2[j-1]) {
                dp[j] = prev + 1;
            } else {
                dp[j] = std::max(dp[j], dp[j-1]);
            }
            prev = temp;
        }
    }
    
    return dp[n];
}

int main() {
    std::string text1 = "abcde";
    std::string text2 = "ace";
    std::cout << "Length of LCS: " << longestCommonSubsequence(text1, text2) << std::endl;
    return 0;
}

3. 总结

本文详细介绍了如何使用C++解决最长上升子序列（LIS）和最长公共子序列（LCS）问题。通过动态规划的方法，我们可以有效地解决这两个经典问题。对于LIS问题，我们还可以通过二分查找进一步优化时间复杂度。对于LCS问题，我们可以通过滚动数组的方式优化空间复杂度。希望本文的内容能够帮助读者更好地理解和掌握这两个问题的解决方法。