【资源限制】

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

【问题描述】

        L星球上的生物由蛋蓝质组成，每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。

        生物学家小乔正在研究L星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列，想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。

        具体的，一个蓝肽可以使用1至5个英文字母表示，其中第一个字母大写，后面的字母小写。一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。

        在一条蓝肽序列中，如果选取其中的一些位置，把这些位置的蓝肽取出，并按照它们在原序列中的位置摆放，则称为这条蓝肽的一个子序列。蓝肽的子序列不一定在原序列中是连续的，中间可能间隔着一些未被取出的蓝肽。

        如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等，则称为一个公共蓝肽子序列。

        给定两条蓝肽序列，找出他们最长的那个公共蓝肽子序列的长度。

【输入格式】

        输入两行，每行包含一个字符串，表示一个蓝肽序列。字符串中间没有空格等分隔字符。

【输出格式】

        输出一个整数，表示最长的那个公共蓝肽子序列的长度。

【样例输入】

LanQiaoBei

LanTaixiaoQiao

【样例输出】

2

【样例说明】

        最长的公共蓝肽子序列为LanQiao，共两个蓝肽。

【评测用例规模与约定】

        对于20%的评测用例，两个字符串的长度均不超过20。

        对于50%的评测用例，两个字符串的长度均不超过100。

        对于所有评测用例，两个字符串的长度均不超过1000。

【思路与分析】

        看似该题引入了几个较为陌生的概念，什么“蛋蓝质”、“蓝肽序列”。其实不去管它这些术语，通过样例便能看出些端倪。这本质上不就是公共子序列嘛！要透过现象看本质，透过晦涩难懂的术语看题目。公共子序列的求解还是比较简单的，直接上代码。

【代码】

import java.util.Scanner;public class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str1 = sc.nextLine();String str2 = sc.nextLine();int num1 = str1.length();int num2 = str2.length();int n = 0;int m = 0;int[] flags1 = new int[num1+1];int cnt = 0;for(int i = 0;i

int[][] dp = new int[n+1][n+1];for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){if(str.charAt(i-1) == rs.charAt(j-1)){dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1] + 1);}else{dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}}