当前位置：网站首页>最长公共子序列(一)(动规)

最长公共子序列(一)(动规)

2022-04-21 12:17:00 【4nc414g0n】

最长公共子序列(一)

题目链接
题目描述：
给定两个字符串 s1 和 s2，长度为m和n 。求两个字符串最长公共子序列的长度。
所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。例如：字符串 “arcaea” 的子序列有 “ara” “rcaa” 等。但 “car” “aaae” 则不是它的子序列。
所谓 s1 和 s2 的最长公共子序列，即一个最长的字符串，它既是 s1 的子序列，也是 s2 的子序列。
数据范围 : 0\leq m,n\leq 10000≤m,n≤1000 。保证字符串中的字符只有小写字母。
要求：空间复杂度 O(mn)O(mn)，时间复杂度 O(mn)O(mn)
进阶：空间复杂度 O(min(m,n))O(min(m,n))，时间复杂度 O(mn)O(mn)
输入：
"abcde","bdcaaa"
输出：
2

思路：

  1. s1:bcde s2:bdc在这里插入图片描述
  2. 状态方程：dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    代码如下：
class Solution {
     
public:
   int LCS(string s1, string s2) {
     
       vector<vector<int>>dp(s1.size()+1,vector<int>(s2.size()+1,0));
       int n1=s1.size(),n2=s2.size();
       for(int i=1;i<=n1;i++)
       {
     
           for(int j=1;j<=n2;j++)
               if(s1[i-1]!=s2[j-1])
                   dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
           else dp[i][j]=dp[i-1][j-1]+1;
       }
       return dp[n1][n2];
   }
}; 
``

版权声明
本文为[4nc414g0n]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_41420788/article/details/124197034

边栏推荐

猜你喜欢

随机推荐