当前位置:网站首页>最长公共子序列(LCS)(动态规划,递归)
最长公共子序列(LCS)(动态规划,递归)
2022-07-06 23:08:00 【疯疯癫癫才自由】
1)从前往后递推:
- 状态设计:dp[i][j]表示两个序列从首位置开始,第一个序列到i-1位置, 第二个到j-1位置的最长公共子序列;
- 状态转移方程: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]);
- 边界:dp[0][j]=dp[i]=0;(i=0...len1,j=0...len2);
- 最后可根据dp[i][j]的值输出最长公共子序列的内容,当dp[i][j]== (dp[i-1][j] || dp[i][j-1]时,明显str1[i]!=str[j];当dp[i][j]==dp[i-1][j-1]时,明显str1[i]==str2[j],那么就把这个元素加到 str中。
- 当然,如果从前往后递推,字符的下标是从1开始的,那么状态设计可以这么表示:状态设计:dp[i][j]表示两个序列从首位置开始,第一个序列到i位置,第二个到j位置的最长公共子序列;而我下面的 程序输入的字符下标是从0开始输入的。
/**
1)状态设计:dp[i][j]表示两个序列从首位置开始,第一个序列到i-1位置,
第二个到j-1位置的最长公共子序列;
状态转移方程: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]);
边界:dp[0][j]=dp[i]=0;(i=0...len1,j=0...len2);
最后可根据dp[i][j]的值输出最长公共子序列的内容,当dp[i][j]==
(dp[i-1][j] || dp[i][j-1]时,明显str1[i]!=str[j];当dp[i][j]
==dp[i-1][j-1]时,明显str1[i]==str2[j],那么就把这个元素加到
str中。
当然,如果从前往后递推,字符的下标是从1开始的,那么状态设计
可以这么表示:状态设计:dp[i][j]表示两个序列从首位置开始,
第一个序列到i位置,第二个到j位置的最长公共子序列;而我下面的
程序输入的字符下标是从0开始输入的。
*/
/**
#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]表示两个序列从首位置开始,第一个序列到i-1位置,第二个到j-1位置
string str; //的最长公共子序列
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;) //似乎又有two point 的影子
{
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)从后往前推;
状态设计:dp[i][j]表示两个序列从尾位置开始,第一个序列到i位置,
第二个到j位置的最长公共子序列;
状态转移方程: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]);
最后可根据dp[i][j]的值输出最长公共子序列的内容,当dp[i][j]==
(dp[i+1][j] || dp[i][j+1]时,明显str1[i]!=str[j];当dp[i][j]
==dp[i-1][j-1]时,明显str1[i]==str2[j]。
/**
2)从后往前推;
状态设计:dp[i][j]表示两个序列从尾位置开始,第一个序列到i位置,
第二个到j位置的最长公共子序列;
状态转移方程: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]);
最后可根据dp[i][j]的值输出最长公共子序列的内容,当dp[i][j]==
(dp[i+1][j] || dp[i][j+1]时,明显str1[i]!=str[j];当dp[i][j]
==dp[i-1][j-1]时,明显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]表示两个序列从尾位置开始,第一个序列到i位置,第二个到j位置
string str; //的最长公共子序列
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;) //似乎又有two point 的影子
{
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;
}
*/
递归解决:
/**
3)递归解决
*/
#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);
}
}
边栏推荐
- Markdown编辑器
- AttributeError: module ‘torch._ C‘ has no attribute ‘_ cuda_ setDevice‘
- 一文搞懂常见的网络I/O模型
- No experts! Growth secrets for junior and intermediate programmers and "quasi programmers" who are still practicing in Universities
- 5G VoNR+之IMS Data Channel概念
- U++4 接口 学习笔记
- IMS data channel concept of 5g vonr+
- Flask project uses flask socketio exception: typeerror: function() argument 1 must be code, not str
- U++ metadata specifier learning notes
- 批量归一化(标准化)处理
猜你喜欢
为什么很多人对技术债务产生误解
[Android kotlin collaboration] use coroutinecontext to realize the retry logic after a network request fails
How to package the parsed Excel data into objects and write this object set into the database?
Ansible中的inventory主機清單(預祝你我有數不盡的鮮花和浪漫)
【愚公系列】2022年7月 Go教学课程 005-变量
Vscode automatically adds a semicolon and jumps to the next line
Why do many people misunderstand technical debt
Leetcode(417)——太平洋大西洋水流问题
No experts! Growth secrets for junior and intermediate programmers and "quasi programmers" who are still practicing in Universities
Time complexity & space complexity
随机推荐
批量归一化(标准化)处理
U++4 接口 学习笔记
Common Oracle SQL statements
3. Type of fund
STM32 system timer flashing LED
Dynamically generate tables
装饰器基础学习02
offer如何选择该考虑哪些因素
Analyse approfondie de kubebuilder
Flask项目使用flask-socketio异常:TypeError: function() argument 1 must be code, not str
Ansible中的inventory主机清单(预祝你我有数不尽的鲜花和浪漫)
Time complexity & space complexity
[ArcGIS tutorial] thematic map production - population density distribution map - population density analysis
A simple and beautiful regression table is produced in one line of code~
sublime使用技巧
Why do many people misunderstand technical debt
[Android kotlin collaboration] use coroutinecontext to realize the retry logic after a network request fails
STM32F103实现IAP在线升级应用程序
【愚公系列】2022年7月 Go教学课程 005-变量
AttributeError: module ‘torch._C‘ has no attribute ‘_cuda_setDevice‘