当前位置:网站首页>Maximum common subsequence
Maximum common subsequence
2022-07-05 15:26:00 【Xuanhong Zhou】
Actually , I'm already in linear dp This topic has been updated there
The purpose of rewriting here , I really want to roast
why??
I'm really dry today
I would like to ask if the university is not a real place to learn knowledge , Give me some messy hubby classes , Finish some meaningless hobby homework , A development project , Just follow the manual , It's the same as installing the software according to the instructions , Is it helpful for me ??? I have to thank my roommate and my classmates here , It's them help My homework , Let me not make these hobbit things every day , I can find time to do what I want to do , Learn the real , Helpful , Wonderful science . Although just a beginner , I also believe that I can gain something , I hope I can become a person like teachers in the future . A recent paper , Now it's written part Some difficulties , Although it is only a summary , But the process of writing an overview is really more painful than a technical article , Suffering from the pain that I can't seem to learn anything , You have to keep checking the information , I want to finish this paper independently , It is estimated that you may have to look at at at least 500 or 600 articles , To quote more than 100 articles , Come on! !
Then I have to write a report , A total of more than ten pages , Not much at all , Hands won't be tired , Because I'm unconscious .
And in class , Model electricity makes my nerves weak , I don't want to see it every day , Always push and drag tomorrow , Shall I watch it tomorrow ? I still don't watch . But I must watch it later ! Big things have to be reviewed , Tomorrow's exam ! Speechless ! Put in a word , Big stuff seems useless for my future study .
Level 6 preparation is rotten , In fact, now 560+ Maybe enough ? But you have to be prepared for nothing , I'm going to prepare this time , I have to take the exam next semester anyway
That's all , Typing is quite cool , Let's take a look at the heavy fog and model electricity again tonight ,vpn If I can't get in, I can't get on Google scholar ah !
Come on! !( It looks like a sprint )
subject
On the largest common word sequence See linearity by yourself dp That article !!!! I like that article very much , Why are there so few visitors metaverse That article has reached 1200 many , It's really popular metaverse!
Code
/* Given two lengths, they are N and M String A and B Seeking both A The subsequence of is B What is the longest string length of the subsequence of . Input format The first line contains two integers N and M. The second line contains a length of N String , Representation string A. The third line contains a length of M String , Representation string B. Strings are made up of lowercase letters . */
/* Be careful : Here is the public sequence , Not substring , Not necessarily adjacent One 、 State means dp[i][j] Express a Before i and b Before j A set of common sequences dp[i][j] The value of is the maximum length of these common sequences Two 、 State transition equation For a dp[i][j], We need to divide By the end of a[i] And the b[j] Elements Four situations : a[i] Packages are not included in the longest common sequence (0,1) b[j] Packages are not included in the longest common sequence (0,1) 1. 00 dp[i][j]=dp[i-1][j-1] #2 and 3 Want to review the online class 2. 01 dp[i-1][j] 3. 10 dp[i][j-1] 4. 11 Satisfy a[i]=b[j] dp[i][j]=dp[i-1][j-1]+1 */
#include<iostream>
using namespace std;
const int Num=2000;
int N,M;
char a[Num],b[Num];
int dp[Num][Num];
int main(){
cin>>N>>M;
getchar();
for(int i=1;i<=N;i++)
scanf("%c",&a[i]);
getchar();
for(int i=1;i<=M;i++)
scanf("%c",&b[i]);
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++){
if(a[i]==b[j])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j-1],max(dp[i-1][j],dp[i][j-1]));
}
cout<<dp[N][M]<<endl;
return 0;
}
边栏推荐
- Object. defineProperty() - VS - new Proxy()
- The difference between SQL Server char nchar varchar and nvarchar
- I spring and autumn blasting-2
- 机器学习框架简述
- I collect multiple Oracle tables at the same time. After collecting for a while, I will report that Oracle's OGA memory is exceeded. Have you encountered it?
- 如何将 DevSecOps 引入企业?
- Ctfshow web entry command execution
- 12 MySQL interview questions that you must chew through to enter Alibaba
- D-snow halo solution
- Transfer the idea of "Zhongtai" to the code
猜你喜欢
1330:【例8.3】最少步数
Talk about your understanding of microservices (PHP interview theory question)
【jvm】运算指令
Creation and optimization of MySQL index
Nine hours, nine people, nine doors problem solving Report
Aike AI frontier promotion (7.5)
30岁汇源,要换新主人了
机器学习笔记 - 灰狼优化
JS knowledge points-01
Database learning - Database Security
随机推荐
mapper.xml文件中的注释
Super wow fast row, you are worth learning!
亿咖通科技通过ISO27001与ISO21434安全管理体系认证
Crud de MySQL
做研究无人咨询、与学生不交心,UNC助理教授两年教职挣扎史
Stm32+bh1750 photosensitive sensor obtains light intensity
Appium自动化测试基础 — APPium基础操作API(二)
Select sort and bubble sort
当代人的水焦虑:好水究竟在哪里?
Redis distributed lock principle and its implementation with PHP (1)
Bugku's steganography
Thymeleaf uses background custom tool classes to process text
Common MySQL interview questions (1) (written MySQL interview questions)
Summary of the third class
SQL Server learning notes
Mysql---- function
F. Weights assignment for tree edges problem solving Report
go学习 ------jwt的相关知识
Bugku's Ah Da
I spring and autumn blasting-1