当前位置：网站首页>[dynamic programming]dp19 longest common subsequence (I) - medium

[dynamic programming]dp19 longest common subsequence (I) - medium

2022-07-18 17:51:00 【51CTO】

describe

Given two strings s1 and s2, The length is n and m . Find the length of the longest common subsequence of two strings .

So called subsequences , Refers to the deletion of some characters from a string （ It's also possible to delete ） Formed string . for example ： character string "arcaea" The subsequences of are "ara" 、 "rcaa" etc. . but "car" 、 "aaae" Is not its subsequence .

So-called s1 and s2 The longest common subsequence of , That is, the longest string , It is both s1 The subsequence , It's also s2 The subsequence .

Data range : . Only lowercase characters in the string are guaranteed .

requirement ： Spatial complexity , Time complexity

Advanced ： Spatial complexity , Time complexity

Input description ：

Enter an integer in the first line n and m , Representation string s1 and s2 The length of .

Next, enter a string in the second and third lines respectively s1 and s2.

Output description ：

Output the length of the longest common subsequence of two strings

Example 1

Input ：

       
       5 6
       
abcde
       
bdcaaa
      
1.
2.
3.

Copy

Output ：

Copy

explain ：

       
        The longest common subsequence is  "bc"  or  "bd" , The length is 2
      
1.

Example 2

Input ：

Copy

Output ：

Answer key

Dynamic programming solution

step ：

Definition dp[i][k] Representation string a And string b The lengths are i and k When , The longest substring length
initialization :dp[0][k] = 0,dp[i][0] = 0, Indicates that a string is 0 When , The length of the longest matching substring with another string is 0
The recursive formula ：

If a[i-1] be equal to b[k-1], Indicates that the current character matches ,dp[i][k] = dp[i-1][k-1]+1
otherwise ,dp[i][k] be equal to max(dp[i][k-1],dp[i-1][k])

The code is as follows ：

       
       #include <bits/stdc++.h>
       
       int 
       
       solve(
       
       const 
       
       std::string 
       
       &
       
       a, 
       
       const 
       
       std::string 
       
       &
       
       b)
       
{
       
       if (
       
       a.
       
       size() 
       
       == 
       
       0 
       
       || 
       
       b.
       
       size() 
       
       == 
       
       0)
       
  {
       
       return 
       
       0;
       
  }
       
       // dp[i][k] Indicates when the length is i Of a in , And length k Of b in , The longest number that can be matched 
       
       std::vector
       
       <
       
       std::vector
       
       <
       
       int
       
       >> 
       
       dp(
       
       a.
       
       size() 
       
       + 
       
       1, 
       
       std::vector
       
       <
       
       int
       
       >(
       
       b.
       
       size() 
       
       + 
       
       1, 
       
       0));
       
       int 
       
       len 
       
       = 
       
       0;
       
       for (
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= 
       
       a.
       
       size(); 
       
       ++
       
       i)
       
  {
       
       for (
       
       int 
       
       k 
       
       = 
       
       1; 
       
       k 
       
       <= 
       
       b.
       
       size(); 
       
       ++
       
       k)
       
    {
       
       if (
       
       a[
       
       i 
       
       - 
       
       1] 
       
       == 
       
       b[
       
       k 
       
       - 
       
       1])
       
      {
       
       dp[
       
       i][
       
       k] 
       
       = 
       
       dp[
       
       i 
       
       - 
       
       1][
       
       k 
       
       - 
       
       1] 
       
       + 
       
       1;
       
      }
       
       else
       
      {
       
       dp[
       
       i][
       
       k] 
       
       = 
       
       std::max(
       
       dp[
       
       i 
       
       - 
       
       1][
       
       k], 
       
       dp[
       
       i][
       
       k 
       
       - 
       
       1]);
       
      }
       
    }
       
  }
       
       return 
       
       dp[
       
       a.
       
       size()][
       
       b.
       
       size()];
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       m, 
       
       n;
       
       std::cin 
       
       >> 
       
       m 
       
       >> 
       
       n;
       
       std::string 
       
       a;
       
       std::string 
       
       b;
       
       std::cin 
       
       >> 
       
       a 
       
       >> 
       
       b;
       
       std::cout 
       
       << 
       
       solve(
       
       a, 
       
       b) 
       
       << 
       
       std::endl;
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.