最长公共子序列问题

同样的，刷题记录。leetcode上的LCS问题。

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

对于子序列问题一般求解都采用动态规划来求解。dp[i][j]表示text1[0...i]与text2[0...j]之间最长的公共子序列的长度。

首先，确定base case：

dp[0][i]=0,dp[i][0]=0. 即，有一个串为空的时候，长度为0；

然后，确定状态转移方程：

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

解释一下，我们求dp[i][j]的时候就是求text1[0...i]与text2[0...j]之间最长的公共子序列的长度，它与dp[i-1][j-1]的关系就取决与text1[i]和text2[j]是否相等，相等，则公共子序列在原来的基础上+1，如果不等，那么就取dp[i-1][j]和dp[i][j-1]的最大值。根据我们的状态转移方程，构造我们的dp table，如下。

text1 ext2	""	a	c	e
""	0	0	0	0
a	0	1	1	1
b	0	1	1	1
c	0	1	2	2
d	0	1	2	2
e	0	1	2	3

贴上二维dp的代码：

 1 int longestCommonSubsequence(string text1, string text2) {
 2         int m=text1.length();
 3         int n=text2.length();
 4         if(m==0||n==0)
 5             return 0;
 6         int dp[m+1][n+1];
 7         for(int i=0;i<=n;i++){
 8             dp[0][i]=0;
 9         }
10         for(int i=0;i<=m;i++){
11             dp[i][0]=0;
12         }
13         for(int i=1;i<=m;i++){
14             for(int j=1;j<=n;j++){
15                 if(text1[i-1]==text2[j-1])
16                     dp[i][j]=dp[i-1][j-1]+1;
17                 else{
18                     dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
19                 }
20             }
21         }
22         return dp[m][n];
23 }

状态压缩之后的代码：

 1 int longestCommonSubsequence(string text1, string text2) {
 2         int m=text1.length();
 3         int n=text2.length();
 4         vector<int>dp(n+1,0);
 5         int last,temp;
 6         for(int i=1;i<=m;i++,last=0){
 7             for(int j=1;j<=n;j++){
 8                 temp=dp[j];
 9                 if(text1[i-1]==text2[j-1])
10                     dp[j]=last+1;
11                 else
12                     dp[j]=max(dp[j],dp[j-1]);
13                 last=temp;
14             }
15         }
16         return dp[n];
17 }