上海企业网站制作费用,农业信息网站建设,如何设计一个logo,网站生成app要多少钱最长公共子序列
题目描述
给定两个长度分别为 N 和 M 的字符串 A 和 B#xff0c;求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。 输入格式
第一行包含两个整数 N和 M。
第二行包含一个长度为 N 的字符串#xff0c;表示字符串 A。
第三行包含一个长度为 M …最长公共子序列
题目描述
给定两个长度分别为 N 和 M 的字符串 A 和 B求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。 输入格式
第一行包含两个整数 N和 M。
第二行包含一个长度为 N 的字符串表示字符串 A。
第三行包含一个长度为 M 的字符串表示字符串 B。
字符串均由小写字母构成。 输出格式
输出一个整数表示最大长度。 数据范围
1≤N,M≤1000
输入样例
4 5 acbd abedc
输出样例
3
状态表示
集合所有从A[1,i] B[1,j]的公共子序列的集合
属性max
像最长上升子序列状态的划分依据是找不同的点。最长上升子序列确定以a[i]为结尾的子序列共同点便是以a[i]作为结尾。划分依据a[1,i-1]中的每个数作为最后一个不同点进行划分** 有没有发现
DP基操
1.找不同和相同之处/不同和固定之处 2.结合定义出发 最长公共子序列的不同点在于i,j在不在序列中可以将集合划分为4类。 实际上只有3类且往下看。 (1)i、j 均不在
i、j均不包含其中那只能从a[i-1]、b[j-1]中去选 得到如下状态转移方程: f [ i ] [ j ] f [ i − 1 ] [ j − 1 ] f[i][j]f[i-1][j-1] f[i][j]f[i−1][j−1] (2)i不在j在
i不在序列中只能从前i-1中选j可在可不在。
刚好i不在j在包含在这种情况中且最大值/最小值是可以允许重复的。 得到如下状态转移方程: f [ i ] [ j ] f [ i − 1 ] [ j ] f[i][j]f[i-1][j] f[i][j]f[i−1][j] (3)i在j不在
j不在序列中那j只能从j-1中选择。i可在可不在。
刚好**i在j**不在包含在这种情况中且最大值/最小值是可以允许重复的。 得到如下状态转移方程: f [ i ] [ j ] f [ i ] [ j − 1 ] f[i][j]f[i][j-1] f[i][j]f[i][j−1]
(4)i、j均在
只有满足**a[i]b[j]这一条件才存在。
确定了**a[i]、b[j]之后剩下的从i-1、j-1中选出最长公共子序列从定义出发恰好就是f[i-1][j-1]中选。最后再加上固定好的a[i]、b[j]这一对即可。 得到如下状态转移方程: f [ i ] [ j ] f [ i − 1 ] [ j − 1 ] 1 f[i][j]f[i-1][j-1]1 f[i][j]f[i−1][j−1]1 最后(1)是既可以包含在(2)也可以包含在(3)中的允许最值重复。重复没关系求出的必定是最值且包含在整个集合中是合法的。最后总共只有3种情况。
求和/求值则不允许重复
Accode
import java.util.*;
public class Main{static int N1010;static int f[][]new int[N][N];public static void main(String []args){Scanner scnew Scanner(System.in);int nsc.nextInt();int msc.nextInt();char a[]( sc.next()).toCharArray();char b[]( sc.next()).toCharArray();for(int i1;in;i){for(int j1;jm;j){//情况1包含在情况2、3中//情况2、3取一个maxf[i][j]Math.max(f[i-1][j],f[i][j-1]);//满足a[i]b[j]这一条件//再与情况4取一个maxif(a[i]b[j])f[i][j]Math.max(f[i][j],f[i-1][j-1]1);}}//输出集合定义System.out.println(f[n][m]); }
}往期回顾
不清楚蓝桥杯考什么的点点下方
考点秘籍
想背纯享模版的伙伴们点点下方
蓝桥杯省一你一定不能错过的模板大全(第一期)
蓝桥杯省一你一定不能错过的模板大全第二期
蓝桥杯省一你一定不能错过的模板大全第三期
蓝桥杯省一你一定不能错过的模板大全第四期
想背注释模版的伙伴们点点下方
蓝桥杯必背第一期
蓝桥杯必背第二期
往期精彩回顾
蓝桥杯上岸每日N题 第一期(一)
蓝桥杯上岸每日N题第一期(二)
蓝桥杯上岸每日N题第一期(三)
蓝桥杯上岸每日N题第二期(一)
蓝桥杯上岸每日N题第三期(一)
蓝桥杯上岸每日N题 第四期(最少刷题数)
蓝桥杯上岸每日N题 第五期(山)
蓝桥杯上岸每日N题 第六期(求阶乘)
蓝桥杯上岸每日N题 第七期(小猫爬山)
蓝桥杯上岸每日N题 第八期 (全球变暖)
蓝桥杯每日N题 (消灭老鼠)
蓝桥杯每日N题杨辉三角形
蓝桥杯每日N题 (砝码称重)
蓝桥杯上岸每日N题(鸡尾酒)
操作系统期末题库 第九期(完结)
LeetCode Hot100 刷题(第三期)
idea创建SpringBoot项目报错解决方案
数据库SQL语句期末冲刺
想看JavaB组填空题的伙伴们点点下方
填空题
竞赛干货
算法竞赛字符串常用操作大全
蓝桥杯上岸必刷(模拟/枚举专题)
蓝桥杯上岸必背 (第三期 DP)
蓝桥杯上岸必背(第四期DFS)
蓝桥杯上岸必背(第五期BFS)
蓝桥杯上岸必背(第六期树与图的遍历)
蓝桥杯上岸必背(第七期 最短路算法)
蓝桥杯上岸必背(第八期 简单数论)
蓝桥杯上岸必刷(进制、数位专题)
蓝桥杯上岸考点清单 (冲刺版
蓝桥杯上岸必背模板 (纯享版
