最長公共子序列

題目描述

給出1,2,…,n 的兩個排列P1 和 P2 ，求它們的最長公共子序列。

輸入格式

第一行是一個數(shù) n。

接下來兩行，每行為 n 個數(shù)，為自然數(shù)1,2,…,n 的一個排列。

輸出格式

一個數(shù)，即最長公共子序列的長度。

題目分析

第一階段定義dp數(shù)組

（1）考慮規(guī)模。兩個序列的長度就是規(guī)模，因為是兩個，所以需要兩個維度來表示。

（2）考慮限制。這里的限制就是對應位置相等，可以在遞推的時候進行限制。

（3）寫dp數(shù)組。$dp[i][j]$表示的第一個序列前i個值和第二個序列前j個值對應的最長公共子序列

第二階段推導狀態(tài)轉(zhuǎn)移方程

（1）如果$s1[i]==s2[j]，dp[i][j]=dp[i?1][j?1]+1$

（1）如果$s1[i]!=s2[j]$，那么我們就要從前一個狀態(tài)的最大值里面轉(zhuǎn)移過來，前一個狀態(tài)有哪些呢？$dp[i?1][j],dp[i][j?1]$就是它的前一個狀態(tài)，$dp[i?1][j?1]$不是，因為他距離$dp[i?1][j?1]$已經(jīng)變化了2步。$dp[i][j]=max(dp[i?1][j],dp[i][j?1])$

第三階段寫代碼

（1）初始化。一開始長度是0。

（2）第一層for循環(huán)遍歷規(guī)模，這里規(guī)模是兩個維度表示的，所以也需要兩層for循環(huán)。

（3）第二層for循環(huán)仍然遍歷規(guī)模。

題目代碼

import java.io.IOException;
import java.util.Scanner;

public class Main{
public static void main(String[] args) throws NumberFormatException, IOException {
	Scanner scanner = new Scanner(System.in);
	int n = scanner.nextInt();
	int m=n;
	int a[] = new int[n+1];
	int b[] = new int[m+1];
	int dp[][] = new int[n+1][m+1];
	for(int i = 1;i <= n;i++) 
		a[i] = scanner.nextInt();
	for(int i = 1;i <= m;i++) 
		b[i] = scanner.nextInt();
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= m;j++) {
			if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
			else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
		}
	}
	System.out.println(dp[n][m]);
}
}

在洛谷提交還是內(nèi)存超限，離譜。

最長公共子串

題目分析

注意子串和子序列的差別，abcde中acd是一個子序列，但不是一個子串，abc是一個子串也是一個子序列。子串的要求要比子序列高。子串必須是連續(xù)的。那么這一點體現(xiàn)在哪里呢。體現(xiàn)在狀態(tài)轉(zhuǎn)移方程以及答案上。

第一階段定義dp數(shù)組

（1）考慮規(guī)模。兩個序列的長度就是規(guī)模，因為是兩個，所以需要兩個維度來表示。

（2）考慮限制。這里的限制就是對應位置相等，可以在遞推的時候進行限制。

（3）寫dp數(shù)組。$dp[i][j]$表示的第一個序列前i個值和第二個序列前j個值對應的最長公共子串

第二階段推導狀態(tài)轉(zhuǎn)移方程

（1）如果

（1）如果

第三階段寫代碼

（1）初始化。一開始長度是0。

（2）第一層for循環(huán)遍歷規(guī)模，這里規(guī)模是兩個維度表示的，所以也需要兩層for循環(huán)。

（3）第二層for循環(huán)仍然遍歷規(guī)模。

（4）答案。這里的$dp[i][j]$不一定是最終答案，答案要在過程中記錄一個最大值。也就是所有dp值的最大值。$max(dp[i][j])$。文章來源地址http://www.zghlxwxcb.cn/news/detail-825112.html

題目代碼

package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
public class Main{
public static void main(String[] args) throws NumberFormatException, IOException {
	Scanner scanner = new Scanner(System.in);
	char a[];
	char b[];
	a = (" "+scanner.next()).toCharArray();
	b = (" "+scanner.next()).toCharArray();
	int n = a.length-1;
	int m = b.length-1;
	int dp[][] = new int[n+1][m+1];	
	int ans = 0;
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= m;j++) {
			if(('0'<=a[i]&&a[i]<='9') || ('0'<=b[j]&&b[j]<='9')) continue;
			if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
			else dp[i][j] = 0;
			ans = Math.max(ans, dp[i][j]);
		}
	}
	System.out.println(ans);
}
}

到了這里，關于最長公共子序列和最長公共子串的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！