首页 > 其他分享 >每日OJ_牛客_最长公共子序列(dp模板)

每日OJ_牛客_最长公共子序列(dp模板)

时间:2024-09-03 20:54:50浏览次数:17  
标签:OJ int 牛客 公共 序列 最长 dp

目录

牛客_最长公共子序列(dp模板)

解析代码


牛客_最长公共子序列(dp模板)

最长公共子序列__牛客网


解析代码

子序列即两个字符串中公共的 字符,但不一定连续。

        从题干中可以提取出问题:求字符串s和t的最长公共子序列 假设LCS(m,n)为长度为m的字符串s与长度为n的字符串t的最长公共子序列,直接进行求解时不太 好求解,那么可以将问题简化为其子问题,假设s和t的长度为任意值i和j,即求LCS(i,j):

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int LCS(const string& m, const string& n)
{	// Longest common subsequence
	int n1 = m.size(), n2 = n.size();
	vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
	for (int i = 1; i <= n1; ++i)
	{
		for (int j = 1; j <= n2; ++j)
		{
			if (m[i - 1] == n[j - 1])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}
	return dp[n1][n2];
}

int main()
{
	string m, n;
	while (cin >> m >> n)
	{
		cout << LCS(m, n) << endl;
	}
	return 0;
}

标签:OJ,int,牛客,公共,序列,最长,dp
From: https://blog.csdn.net/GRrtx/article/details/141818766

相关文章

  • POJ - 1765
    第一次做扫描线挺好的#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;structppx{ intl,r; doubleleft,right; doublelen; intcover;//记录重边情况}tree[4*200+10];doubley[200+10];//对应的序号装对应的边structpp{ doublex......
  • zdppy+vue3+onlyoffice文档管理系统实战 20240902 上课笔记 登录功能优化
    遗留问题1、登录以后跳转最近文档2、如果用户没有登录应该自动跳转登录页面3、如果用户的token校验失败,应该自动调整登录界面4、按回车键自动跳转登录页面登录以后跳转最近文档constrouter=useRouter()router.push("/")实际代码:constloginData=awaitapi.login......
  • 使用LangChain加载Project Gutenberg电子书:实用指南
    使用LangChain加载ProjectGutenberg电子书:实用指南引言ProjectGutenberg是一个提供免费电子书的在线图书馆,拥有超过60,000本电子书。对于自然语言处理(NLP)和文本分析项目来说,这是一个宝贵的资源。本文将介绍如何使用LangChain的GutenbergLoader来加载ProjectGutenberg的......
  • POJ - 1870
    先把蜂巢快递柜画出来:__________/\__/\__/\__/\____/\__/\__/53\__/\__/\__/\__/\__/52\__/54\__/\__/\\__/\__/51\__/31\__/55\__/\__//\__/50\__/30\__/32\__/56\__/\\__/49\__/29\__......
  • winform实时获取系统dpi
    环境:window10框架:4.5.2由于windows10的DPI设置无法直接获取屏幕的真实长宽获取长宽代码intiH=Screen.PrimaryScreen.Bounds.Height;intiW=Screen.PrimaryScreen.Bounds.Width;两种方法:1、使用上边代码获取缩放后的长宽iH*DPI(1.25)=真实高度DPI获取方法:#reg......
  • POJ - 3318
    他说:O(n^3)是过不了滴一搜……6代码和题解没有实质区别:#include<cstdio>#include<ctime>#include<cstdlib>usingnamespacestd;inta[505][505],b[505][505],c[505][505];intmain(){ srand(time(NULL)); intn; ios::sync_with_stdio(0); cin.tie(0); while(cin......
  • POJ - 2976
    原来是二分谁对平均分贡献大选谁界限<0.001,100次足矣#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;constintmaxn=1010;intn,k;doublemid;structNode{ doublea,b;}w[maxn];boolcmp(Nodex,Nodey......
  • 产品经理必看!超详细的NPDP认证考试科普
    能力提升是每个职场人最关心的问题,产品经理当然也不例外。相信不少朋友在走上产品的道路后都是边做边学边摸索。特别是刚工作5年内的PM,对产品的整个知识框架并不成熟,1000个产品经理,就有1000个产品问题。但所有问题的本质,都是因为缺少系统的产品管理知识体系、解决问题的原则方法、......
  • 产品经理必看!超详细的NPDP认证考试科普
    能力提升是每个职场人最关心的问题,产品经理当然也不例外。相信不少朋友在走上产品的道路后都是边做边学边摸索。特别是刚工作5年内的PM,对产品的整个知识框架并不成熟,1000个产品经理,就有1000个产品问题。但所有问题的本质,都是因为缺少系统的产品管理知识体系、解决问题的原则方法、......
  • HivisionIDPhotos :一款开源的轻量级且高效的AI证件照制作工具
    HivisionIDPhotos是一款开源的轻量级且高效的AI证件照制作工具,它通过AI算法实现了对多种用户拍照场景的识别、抠图以及证件照生成。这款工具能够根据不同的尺寸规格生成标准证件照和排版照,适用于护照、签证等多种用途。HivisionIDPhotos的主要特点包括轻量级抠图、生成标准证......