18308 最长公共子序列 Description 将两个字符串的公共子序列问题拆分为前i个字符中最长的公共子序列问题,进行动态规划。 第一次尝试写东西发csdn…只是复习的时候遇到的关于动态规划的题…希望能对你有帮助~原题
时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC;VC
给定两个字符串,请输出这两个字符串的最大公共子序列
输入格式
两行,一行一个字符串(不包括空格,Tab键),长度不超过1000
输出格式
输出最大公共子序列的长度
输入样例
abbca
aba
输出样例
3思路
(可以想像到,起点即为a[0]与b[0],终点即为a[m]和b[n])
代码
// LongestPublicSonSq.cpp #include <iostream> #include <cstring> using namespace std; char a[1000]; char b[1000]; int maxLen[1000][1000]; int main() { cin>>a>>b; int len1 = strlen(a); int len2 = strlen(b); int i,j; for (i=0; i<=len1;i++) maxLen[i][0] = 0; for (j=0; j<=len2;j++) maxLen[0][j] = 0; for (i=1;i<=len1;i++) { for (j=1;j<=len2;j++) { if (a[i-1]==b[j-1]) maxLen[i][j] = maxLen[i-1][j-1]+1; else { maxLen[i][j] = max(maxLen[i-1][j], maxLen[i][j-1]); } } } cout<<maxLen[len1][len2]<<endl; return 0; }
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)