最长公共子序列

问题描述

• 对于两个字符串，请设计一个高效算法，求他们的最长公共子序列的长度，这里的最长公共子序列定义为有两个序列U1,U2,U3...Un和V1,V2,V3...Vn,其中Ui&ltUi+1，Vi&ltVi+1。且A[Ui] == B[Vi]。
• 输入: "1A2C3D4B56",10,"B1D23CA45B6A",12
• 输出: 6
• 注意: 子序列可以不连续

问题思路

• 简单的动态规划问题, 使用二维数组保存子序列的个数
• F(i, j) 表示A[0-i]和B[0-j]的最长公共子序列的长度

代码实现

int findLCS(string A, int n, string B, int m) {
        if(n <= 0 || m <= 0) {
            return 0;
        }

        std::vector<std::vector<int>> dp(n+1, std::vector<int>(m+1, 0));

        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= m; ++j) {
                if(A[i-1] == B[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[n][m];
    }