欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最长公共子序列

程序员文章站 2024-03-17 22:00:34
...

最长公共子序列

思路:把两个序列的最后一位数进行比较 相等就令公共子序列长度+1,然后再令序列长度减少1再继续比较,如果不相等就分别令其中一个序列长度-1再继续比较,先看递归方式会很好理解

static int[][] memo = new int[1000][1000];
	static int[][] dp = new int[1000][1000];
	//暴力递归
	static int longest(char[] x, char[] y, int lenX, int lenY) {
		if(lenX == -1 || lenY == -1)
			return 0;
		if(x[lenX] == y[lenY]) {
			return longest(x, y, lenX-1,lenY-1)+1;
		}
		return Math.max(longest(x,y,lenX-1, lenY), longest(x,y,lenX,lenY-1));
	}
	//记忆化搜索
	static int longestMemo(char[] x, char[] y, int lenX, int lenY) {
		if(lenX == -1 || lenY == -1)
			return 0;
		else if(x[lenX] == y[lenY]) 
			memo[lenX][lenY] = longestMemo(x, y, lenX-1,lenY-1)+1;
		else
			memo[lenX][lenY] = Math.max(longestMemo(x,y,lenX-1, lenY), longestMemo(x,y,lenX,lenY-1));
		return memo[lenX][lenY];
	}
	//dp
	static void longestDp(char[] x, char[] y, int lenX, int lenY){
		for(int i = 0; i <= lenX; i++) {
			for(int j = 0; j <= lenY;j++) {
				if(x[i] == y[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]);
			}
		}
		System.out.println(dp[lenX+1][lenY+1]);
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String X = sc.nextLine();
		String Y = sc.nextLine();
		System.out.println(longest(X.toCharArray(), Y.toCharArray(), X.length()-1, Y.length()-1));
		System.out.println(longestMemo(X.toCharArray(), Y.toCharArray(), X.length()-1, Y.length()-1));;
		longestDp(X.toCharArray(), Y.toCharArray(), X.length()-1, Y.length()-1);		
		//ABCBDAB
		//BDCABA
	}

我本人做dp的题目 习惯性:暴力递归->记忆化搜索->dp


不喜勿喷