1、思路

• dp[i][j]表示text1[0 ... i]和text2[0 ... j]两个子串的最长公共子序列长度。其中dp[0][...]和dp[...][0]表示其中一个字符串为空的情况，这种情况的最长公共子序列长度为0；

• 状态转移方程分两种情况讨论：
  1、若text1[i] != text2[j]，则dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])；
  2、若text1[i] == text2[j]，则dp[i][j] = dp[i - 1][j - 1] + 1；

• 时间复杂度为 $O(mn)$ ，空间复杂度为 $O(mn)$ 。

2、代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.length(), m = text2.length();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));   //二维数组初始化为0

        for (int i = 1; i <= n; ++ i)
        {
            for (int j = 1; j <= m; ++ j)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                if (text1[i - 1] == text2[j - 1]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }

        return dp[n][m];
    }
};

3、空间优化

• 因为当前状态dp[i][j]只能从dp[i - 1][j - 1]、dp[i - 1][j]和dp[i][j - 1]三个状态转移过来，仅涉及到最新的两行，故可用一个两行n列的二维数组表示；

• 时间复杂度为 $O(mn)$ ，空间复杂度为 $O(n)$ 。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.length(), m = text2.length();
        if (m > n) return longestCommonSubsequence(text2, text1);

        vector<vector<int>> dp(2, vector<int>(n + 1, 0));

        for (int i = 1; i <= n; ++ i)
        {
            for (int j = 1; j <= m; ++ j)
            {
                //dp[i % 2][j]为当前状态，dp[(i + 1) % 2][j]为上一行的状态，dp[i % 2][j - 1]为上一列的状态
                dp[i % 2][j] = max(dp[(i + 1) % 2][j], dp[i % 2][j - 1]);
                if (text1[i - 1] == text2[j - 1]) dp[i % 2][j] = max(dp[i % 2][j], dp[(i + 1) % 2][j - 1] + 1);
            }
        }

        return dp[n % 2][m];
    }
};