1143.最长公共子序列

力扣题目链接(opens new window)

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

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

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

示例 2: 输入：text1 = "abc", text2 = "abc" 输出：3 解释：最长公共子序列是 "abc"，它的长度为 3。

示例 3: 输入：text1 = "abc", text2 = "def" 输出：0 解释：两个字符串没有公共子序列，返回 0。

提示:

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000 输入的字符串只含有小写英文字符

思路

动态规划的思路

五部曲

1.确定dp数组和下标的含义

因为这里有两个字符串，所以我们应该使用二维的数组，即dp[i][j]，i表示第一个字符串的前i个元素，j表示第二个字符串的前j个元素，dp[i][j]表示由第一个字符串的前i个元素和第二个字符串的前j个元素构成的公共子序列的长度

2.确定递推公式

对于dp[i][j],可以由4中情况来决定，dp[i-1][j-1],dp[i-1][j],dp[i][j-1],dp[i][j]，而dp[i-1][j-1]是包含在dp[i-1][j]和dp[i][j-1]中的,所以可以不用考虑，dp[i][j]的情况前提是a[i] == b[j]，然后去三者中的最大值

3.dp数组如何初始化

全部初始化为0即可

4.遍历顺序

先遍历哪一个都可以

5.举例推导dp数组

不在举例，直接给出代码

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 1010;
char a[N],b[N];
int f[N][N];
int n,m;
int main()
{
    cin >> n >> m;
    cin >> a + 1 >> b + 1;

    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            f[i][j] = max(f[i-1][j],f[j-1][i]);
            if (a[i] == b[j])
            {
                f[i][j] = max(f[i][j],f[i-1][j-1] + 1);
            }
        }
    }
    
    cout << f[i][j] << endl;
    return 0;
}