leetcode LCR095. 最长公共子序列

1. 题意

给定两个串$st$,求最长公共子序列长度。

2. 题解

2.1 动态规划

写出状态转移方程
$$dp[i][j]=\{\begin{array}{l}dp[i-1][j-1]+1,s[i-1]==t[j-1]\\ \max (dp[i-1][j],dp[i][j-1]),s[i-1]\ne t[j-1]\end{array}$$

转换为递推即可

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();

        vector< vector<int> > dp(m + 1, vector<int>(n + 1, 0));
        /*dp[0][0] = 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] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

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

2.2 空间优化一

根据动态规划的递推关系，我们可以得到下面的图示关系。

当前行的值事实上只与上一行和本行有关。

所以我们可以用两行的滚动数组进行优化。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();

        vector< vector<int> > dp( 2, vector<int>(n + 1, 0));
        /*dp[0][0] = 0;*/

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

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

2.3 空间优化二

事实上我们甚至并不需要两行。

我们只需要能使得递推能够进行就行。

尝试压到一个数组，当计算到$dp[j]$时，我们会发现。

$$\begin{gathered} dp[j-1]=dp[i][j-1] \\ dp[j]=dp[i-1][j] \end{gathered}$$
我们发现少了一个$dp[i-1][j-1]$, 那它去哪了呢，

它被计算$dp[j-1]$的时候给覆盖了。

所以我们每次计算前需要先保存$dp[j]=dp[i][j]$, 留给$dp[j+1]=dp[i][j+1]$使用。

上代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();
    
        /*dp[0][0] = 0;*/
        vector<int> dp(n + 1, 0);
        
        int pre = 0;

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


        return dp[n];
    }
};

3. 参考

03xf