蓝桥杯算法提高VIP-最长公共子序列（Java代码） 动态规划

解题思路:     DP动态规划

注意事项:

参考代码:

import java.util.Scanner;

/**
 * 2021年2月18日  下午5:19:07
 * @author praguetramp
 */
public class P2086 {
	/*
	 * 给定两个字符串，寻找这两个字串之间的最长公共子序列。
	 */
	public static int LCS(String s1,String s2) {
		int [][] arr = new int[s1.length()+1][s2.length()+1]; 
//		for(int row=0;row<=s1.length();row++)
//			arr[row][0]=0;
//		for(int col=0;col<=s2.length();col++)
//			arr[0][col]=0;
		for(int i=1;i<=s1.length();i++)
			for(int j=1;j<=s2.length();j++) {
				if(s1.charAt(i-1)==s2.charAt(j-1))   //若该字符相同，则长度+1，包含该字符的序列
					arr[i][j] = arr[i-1][j-1]+1;
				else if(arr[i][j-1]>arr[i-1][j])  
					arr[i][j] = arr[i][j-1];
				else
					arr[i][j] = arr[i-1][j];
			}
		return arr[s1.length()][s2.length()];
	}
	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s1 = in.nextLine();
        String s2 = in.nextLine();
        int res = LCS(s1,s2);
        System.out.println(res);
        in.close();
    }
}