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