十一届国赛编程题第一题dp数组

思路：

    开始会想，直接直接从数组a的第i个开始匹配，b设一个str储存当前位置加1，一个个去匹配不好吗？然后就会发现，因为是不连续的，所以会存在拿与不拿的问题，这个时候就该想到dp了。dp的熟悉套路是
    取值情况:两种取值，a的数量和b的数量

    dp代表的值:一般情况都是代表直接求的值，这题就是公共子序列的长度。

    字符串切割就不说了，找到大写，与前一个截取，存入，更新前一个下标，end

    这里记录一下dp[i][j]的思路，肯定是先遍历a的字符串，再在a字符串取一个的情况下对b字符串进行匹配。如果拿到了，那么当前长度的字符串的长度是前一个字符串拿到长度的值+1，如果没拿的话，就看前面dp[i-1][j]大还是dp[i][j-1]大，最后查看两个都遍历完的取值。end

import java.io.*;
import java.util.ArrayList;
public class Main{
	static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	public static void main(String[] args) throws IOException {
		ArrayList a=f(bf.readLine());
		ArrayList b=f(bf.readLine());
		//dp[i][j]的意思是a选到第i个，b选到第j个的最大子序列长度
		//dp[0][0]=0
		int[][] dp=new int[a.size()+1][b.size()+1];
		for(int i=0;i<a.size();i++) {
			for(int j=0;j<b.size();j++) {
				if(a.get(i).equals(b.get(j))) {
					dp[i+1][j+1]=dp[i][j]+1;
				}else {
					dp[i+1][j+1]=Math.max(dp[i][j+1], dp[i+1][j]);
				}
			}
		}
		pw.print(dp[a.size()][b.size()]);
		pw.flush();
	}
	public static ArrayList f(String a) {
		//储存前一个大写字母的位置
		int str=0;
		ArrayList arraylist=new ArrayList<>();
		for(int i=1;i<a.length();i++) {
			if(a.charAt(i)<'a') {		
				String s=a.substring(str,i);
				arraylist.add(s);
				str=i;
			}
		}
		arraylist.add(a.substring(str,a.length()));
		return arraylist;
	}
}