私信TA

用户名:Praguetramp

访问量:29252

签 名:

等  级
排  名 19
经  验 19923
参赛次数 0
文章发表 130
年  龄 0
在职情况 待业
学  校
专  业

  自我简介:

aura

TA的其他文章

解题思路:     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();
    }
}


 

0.0分

1 人评分

  评论区