最长公共子序列
程序员文章站
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
不喜勿喷