当前位置:网站首页>Longest common subsequence (LCS) (dynamic programming, recursive)
Longest common subsequence (LCS) (dynamic programming, recursive)
2022-07-07 05:08:00 【Madness makes freedom】
1) Recursion after going :
- State Design :dp[i][j] Indicates that two sequences start from the first position , The first sequence goes to i-1 Location , The second to j-1 The longest common subsequence of positions ;
- State transition equation :dp[i][j]=dp[i-1][j-1]+1 (str1[i-1]==str2[j-1]);
- || = max(dp[i-1][j],dp[i][j-1]) (str1[i-1]!=str2[j-1]);
- The border :dp[0][j]=dp[i]=0;(i=0...len1,j=0...len2);
- Finally, according to dp[i][j] Output the content of the longest common subsequence , When dp[i][j]== (dp[i-1][j] || dp[i][j-1] when , obvious str1[i]!=str[j]; When dp[i][j]==dp[i-1][j-1] when , obvious str1[i]==str2[j], Then add this element to str in .
- Of course , If you recurs after going , The subscript of the character is from 1 At the beginning , Then state design can be expressed in this way : State Design :dp[i][j] Indicates that two sequences start from the first position , The first sequence goes to i Location , The second to j The longest common subsequence of positions ; And below me The character subscript entered by the program is from 0 Start typing .
/**
1) State Design :dp[i][j] Indicates that two sequences start from the first position , The first sequence goes to i-1 Location ,
The second to j-1 The longest common subsequence of positions ;
State transition equation :dp[i][j]=dp[i-1][j-1]+1 (str1[i-1]==str2[j-1]);
|| = max(dp[i-1][j],dp[i][j-1]) (str1[i-1]!=str2[j-1]);
The border :dp[0][j]=dp[i]=0;(i=0...len1,j=0...len2);
Finally, according to dp[i][j] Output the content of the longest common subsequence , When dp[i][j]==
(dp[i-1][j] || dp[i][j-1] when , obvious str1[i]!=str[j]; When dp[i][j]
==dp[i-1][j-1] when , obvious str1[i]==str2[j], Then add this element to
str in .
Of course , If you recurs after going , The subscript of the character is from 1 At the beginning , So state design
It can be expressed in this way : State Design :dp[i][j] Indicates that two sequences start from the first position ,
The first sequence goes to i Location , The second to j The longest common subsequence of positions ; And below me
The character subscript entered by the program is from 0 Start typing .
*/
/**
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
string str1,str2;
cout << "input two strings:\n";
cin >> str1 >> str2;
int len1=str1.size(),len2=str2.size();
int dp[len1+1][len2+1]; //dp[i][j] Indicates that two sequences start from the first position , The first sequence goes to i-1 Location , The second to j-1 Location
string str; // The longest common subsequence of
for(int i=0;i<=len1;++i)
dp[i][0]=0;
for(int j=0;j<=len2;++j)
dp[0][j]=0;
for(int i=1;i<=len1;++i)
for(int j=1;j<=len2;++j)
{
if(str1[i-1]==str2[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
for(int i=len1,j=len2;i>0&&j>0;) // Seems to have two point Shadow
{
if(dp[i][j]==dp[i-1][j])
--i;
else if(dp[i][j]==dp[i][j-1])
--j;
else
{
str=str1[i-1]+str;
--i;
--j;
}
}
cout << dp[len1][len2] << endl;
cout << str << endl;
cout << "Hello world!" << endl;
return 0;
}
*/
2) Push back and forth ;
State Design :dp[i][j] Indicates that two sequences start from the tail position , The first sequence goes to i Location ,
The second to j The longest common subsequence of positions ;
State transition equation :dp[i][j]=dp[i+1][j+1]+1 (str1[i]==str2[j]);
|| = max(dp[i+1][j],dp[i][j+1]) (str1[i]!=str2[j]);
Finally, according to dp[i][j] Output the content of the longest common subsequence , When dp[i][j]==
(dp[i+1][j] || dp[i][j+1] when , obvious str1[i]!=str[j]; When dp[i][j]
==dp[i-1][j-1] when , obvious str1[i]==str2[j].
/**
2) Push back and forth ;
State Design :dp[i][j] Indicates that two sequences start from the tail position , The first sequence goes to i Location ,
The second to j The longest common subsequence of positions ;
State transition equation :dp[i][j]=dp[i+1][j+1]+1 (str1[i]==str2[j]);
|| = max(dp[i+1][j],dp[i][j+1]) (str1[i]!=str2[j]);
Finally, according to dp[i][j] Output the content of the longest common subsequence , When dp[i][j]==
(dp[i+1][j] || dp[i][j+1] when , obvious str1[i]!=str[j]; When dp[i][j]
==dp[i-1][j-1] when , obvious str1[i]==str2[j].
*/
/**
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
string str1,str2;
cout << "input two strings:\n";
cin >> str1 >> str2;
int len1=str1.size(),len2=str2.size();
int dp[len1+1][len2+1]={0}; //dp[i][j] Indicates that two sequences start from the tail position , The first sequence goes to i Location , The second to j Location
string str; // The longest common subsequence of
for(int i=0;i<=len1;++i)
dp[i][0]=0;
for(int j=0;j<=len2;++j)
dp[0][j]=0;
for(int i=len1-1;i>=0;--i)
for(int j=len2-1;j>=0;--j)
{
if(str1[i]==str2[j])
dp[i][j]=dp[i+1][j+1]+1;
else
dp[i][j]=max(dp[i+1][j],dp[i][j+1]);
}
for(int i=0,j=0;i<len1&&j<len2;) // Seems to have two point Shadow
{
if(dp[i][j]==dp[i+1][j])
++i;
else if(dp[i][j]==dp[i][j+1])
++j;
else
{
str+=str1[i];
++i;
++j;
}
}
cout << dp[0][0] << endl;
cout << str << endl;
cout << "Hello world!" << endl;
return 0;
}
*/
Recursive solution :
/**
3) Recursive solution
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
string str1,str2,str;
int dp[100][100];
int lcs_len(int l1,int l2);
void lcs_str(int l1,int l2);
int main()
{
cout << "input two strings:\n";
cin >> str1 >> str2;
int len1=str1.size(),len2=str2.size();
memset(*dp,-1,sizeof dp);
lcs_len(len1,len2);
lcs_str(len1,len2);
cout << dp[len1][len2] << endl;
cout << str << endl;
cout << "Hello world!" << endl;
return 0;
}
int lcs_len(int l1,int l2)
{
if(dp[l1][l2]!=-1)
return dp[l1][l2];
else
{
if(l1==0||l2==0)
return dp[l1][l2]=0;
if(str1[l1-1]==str2[l2-1])
return dp[l1][l2]=lcs_len(l1-1,l2-1)+1;
else
return dp[l1][l2]=max(lcs_len(l1-1,l2),lcs_len(l1,l2-1));
}
}
void lcs_str(int l1,int l2)
{
if(l1==0||l2==0)
return ;
if(dp[l1][l2]==dp[l1-1][l2])
lcs_str(l1-1,l2);
else if(dp[l1][l2]==dp[l1][l2-1])
lcs_str(l1,l2-1);
else
{
str=str1[l1-1]+str;
lcs_str(l1-1,l2-1);
}
}
边栏推荐
- 第一篇论文的写作流程
- Stm32f103ze+sht30 detection of ambient temperature and humidity (IIC simulation sequence)
- 《二》标签
- Meow, come, come: do you really know if, if else
- [Android kotlin collaboration] use coroutinecontext to realize the retry logic after a network request fails
- PLC模拟量输出 模拟量输出FB analog2NDA(三菱FX3U)
- Why do many people misunderstand technical debt
- 腾讯云数据库公有云市场稳居TOP 2!
- U++4 接口 学习笔记
- 批量归一化(标准化)处理
猜你喜欢
Ansible报错:“msg“: “Invalid/incorrect password: Permission denied, please try again.“
高手勿进!写给初中级程序员以及还在大学修炼的“准程序员”的成长秘籍
《五》表格
Operand of null-aware operation ‘!‘ has type ‘SchedulerBinding‘ which excludes null.
【愚公系列】2022年7月 Go教学课程 005-变量
拿到PMP认证带来什么改变?
《二》标签
Tree map: tree view - draw covid-19 array diagram
IMS data channel concept of 5g vonr+
U++ 游戏类 学习笔记
随机推荐
Leetcode longest public prefix
【ArcGIS教程】专题图制作-人口密度分布图——人口密度分析
Using thread class and runnable interface to realize the difference between multithreading
Ansible报错:“msg“: “Invalid/incorrect password: Permission denied, please try again.“
【736. Lisp 语法解析】
Function pointer and pointer function in C language
JS 的 try catch finally 中 return 的执行顺序
qt 简单布局 盒子模型 加弹簧
STM32F103 realize IAP online upgrade application
Salesforce 容器化 ISV 场景下的软件供应链安全落地实践
基于Bevy游戏引擎和FPGA的双人游戏
Two methods of chromosome coordinate sequencing
01 machine learning related regulations
Leetcode(46)——全排列
App embedded H5 --- iPhone soft keyboard blocks input text
SQL injection HTTP header injection
ThinkPHP关联预载入with
最长回文子串(动态规划)
HarmonyOS第四次培训
全国气象数据/降雨量分布数据/太阳辐射数据/NPP净初级生产力数据/植被覆盖度数据