本文共 1828 字，大约阅读时间需要 6 分钟。

题目：

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence of two strings is a subsequence that is common to both strings.

 

If there is no common subsequence, return 0.

 

Example 1:

Input: text1 = "abcde", text2 = "ace" Output: 3  Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"Output: 3Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"Output: 0Explanation: There is no such common subsequence, so the result is 0.

 

Constraints:

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000
• The input strings consist of lowercase English characters only.

 

思路：

经典DP题。设m为text1的长度，n为text2的长度，建立一个m*n的2-D矩阵。初始化是第一列和第一行，显然只要text1的第一个字母，和text2对上的第一个字母之后的所有[0][j]都是1，同理对上后的所有的[i][0]都为1，否则都应为初始值0。状态转移方程则很简单，对于所有i>=1和j>=1，首先dp[i][j]代表的是text1的前i位和text2前j位的最长公共子序列，那么有，即从两边各自少最后一个字母来看，选最大的作为备选项。如果text1[i]==text2[j]，那么，即如果当前两个字母相等，则从两边同时退一位的格子中取出值，再加1，然后与原本上面比较完的值求最大即可。

 

代码：

class Solution {

public:     int longestCommonSubsequence(string text1, string text2) {         int m=text1.size(), n=text2.size();         vector<vector<int>> dp(m,vector<int>(n));         if(text1[0]==text2[0])             dp[0][0]=1;         for(int i=1;i<m;i++)         {             dp[i][0]=dp[i-1][0];             if(text1[i]==text2[0])                 dp[i][0]=1;         }         for(int j=1;j<n;j++)         {             dp[0][j]=dp[0][j-1];             if(text1[0]==text2[j])                 dp[0][j]=1;         }         for(int i=1;i<m;i++)         {             for(int j=1;j<n;j++)             {                 dp[i][j]=max(dp[i-1][j],dp[i][j-1]);                 if(text1[i]==text2[j])                     dp[i][j]=max(dp[i][j], dp[i-1][j-1]+1);             }         }         return dp[m-1][n-1];     } };