題目描述
我們有兩個字符串m和n蜕着，如果它們的子串a(chǎn)和b內(nèi)容相同躺枕，則稱a和b是m和n的公共子序列家制。子串中的字符不一定在原字符串中連續(xù)暂雹。
例如字符串“abcfbc”和“abfcab”，其中“abc”同時出現(xiàn)在兩個字符串中脓魏，因此“abc”是它們的公共子序列兰吟。此外，“ab”茂翔、“af”等都是它們的字串混蔼。
現(xiàn)在給你兩個任意字符串（不包含空格），請幫忙計算它們的最長公共子序列的長度珊燎。
輸入描述：
輸入包含多組數(shù)據(jù)惭嚣。
每組數(shù)據(jù)包含兩個字符串m和n，它們僅包含字母悔政，并且長度不超過1024晚吞。
輸出描述：
對應(yīng)每組輸入，輸出最長公共子序列的長度卓箫。
實例
輸入
abcfbc abfcab
programming contest
abcd mnp
輸出
4
2
0
解題思路
這道題载矿，要想在本地測試通過自己的測試用例是不難的。但是要完全AC就要注意烹卒，作者就是因為踩了坑闷盔，所以才特地記錄，并稍微深入找了下踩坑原因旅急。先來說一下大致思路：
- 第一點逢勾，動態(tài)規(guī)劃的老套路：畫表格找規(guī)律。至于具體怎么畫表格藐吮，作者也是半瓶水溺拱，這里不展開叫惊，不清楚的可以網(wǎng)上找資料氯材，已經(jīng)有比較多了，或者私信留言作者汤踏。
- 第二點泥从，找邊界條件（或者說出口條件）句占。因為動態(tài)規(guī)劃往往是將大問題分成各個不獨立的子問題，也就是說這個子問題總要有一個是最小的那個子問題躯嫉，然后才去遞歸或者公式推導(dǎo)（這就需要上面的找規(guī)律結(jié)論）纱烘。一般來講，出口條件也基本上是一些邊界值祈餐，比如數(shù)組0,1
- 第三點擂啥，選擇解題方法，主要有兩種方式：（1）遞歸帆阳；（2）矩陣標記值哺壶，推導(dǎo)的方式。
拿這道題舉例來說蜒谤，假設(shè)m,n分別為字符串1（str1）和字符串2(str2)的長度, 設(shè)(m,n)表示str1前m個字符和str2前n個字符的最長子序列.通過找規(guī)律山宾，發(fā)現(xiàn)要求(m,n),則先求解子問題。即這個問題轉(zhuǎn)換為：當兩個字符串長分別為m-1芭逝，n-1求得最長公共子序列塌碌，然后在各自添加一個字符，求解旬盯，即求解(m,n)台妆。這樣一來，問題被分成兩個子問題胖翰，也就是兩種情況接剩，str1新添加的字符與str2新添加的字符是否相等？
相等的情況
(m,n) = (m-1,n-1) + 1（這個1萨咳，表示在原有基礎(chǔ)上有多了一個相等字符懊缺，總數(shù)加1）
不相等的情況
通過規(guī)律發(fā)現(xiàn)，如果各自新加入一個字符字之后不相等，那么此時取該空格處左邊鹃两、上邊兩處空格中的較大值（具體可以先去畫個表格研究下）遗座，即(m,n) = max( (m-1,n), (m,n-1) )
分析完之后是不是比較清晰了呢？下面簡要說一下兩種解決此問題的方法：遞歸俊扳、矩陣標記值（為了好記）
遞歸解題
自頂向下途蒋，比如讓你求(m,n)，然后你要知道（m-1,n-1）(m-2,n-2)...這樣逐層遞歸馋记，知道上面說的跳出條件号坡，這個遞歸才結(jié)束，最后以調(diào)用棧的方式逐層返回值
矩陣標記值
自底向上梯醒。首先從邊界值開始然后填滿 dp（m,n）的矩陣宽堆，最后那個就是要求的值。
我的解題歷程
- 首先茸习，作者習(xí)慣用遞歸來解畜隶，所以一上來就用遞歸走了一波，代碼如下：
import java.util.Scanner;
public class LCSS {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String str1 = sc.next();
String str2 = sc.next();
long start = System.currentTimeMillis();
int m = str1.length();
int n = str2.length();
boolean flag = str1.charAt(0) == str2.charAt(0);
System.out.println(num(str1,str2,m-1,n-1, flag));
System.out.println(System.currentTimeMillis()-start);
}
}
public static int num(String str1, String str2, int m, int n, boolean flag) {
if (m < 1 || n < 1) {
if (flag) {
return 1;
}
else {
return 0;
}
}
if (str1.charAt(m) == str2.charAt(n)) {
return num(str1, str2, m-1, n-1, flag) +1;
} else {
return Math.max(num(str1, str2, m-1, n, flag),num(str1, str2, m, n-1, flag));
}
}
}
但是后來一運行發(fā)現(xiàn)本地用例都ok逮光，但是并沒有AC代箭，因為超時！
后來采用后者涕刚，原因是遞歸的話嗡综，每次計算的結(jié)果并沒有保存下來，會反復(fù)計算（當然也可以通過其他方式優(yōu)化）杜漠，后來作者直接采用矩陣標記計算結(jié)果的方式极景，然后提交就AC了，直接上代碼:
import java.util.Scanner;
public class LCSS2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
String str1 = sc.next();
String str2 = sc.next();
System.out.println(length(str1.toCharArray(), str2.toCharArray()));
}
}
private static int length(char[] str1, char[] str2) {
int m = str1.length;
int n = str2.length;
int[][] dp = new int[m][n];
for (int i = 0; i < m;i++) {
for (int j = 0;j < n; j++) {
if ( i < 1) {
if (str1[0] == str2[j] || str1[0] == str2[0]) {
dp[i][j] = 1;
} else {
dp[i][j] =0;
}
} else if (j < 1) {
if (str1[i] == str2[j] || str2[0] == str1[0] || dp[i-1][0] == 1) {
dp[i][j] = 1;
} else {
dp[i][j] =0;
}
} else {
if (str1[i] == str2[j]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
}
return dp[m-1][n-1];
}
}
踩坑總結(jié)
時間復(fù)雜度
邊界值
適當注意一下邊界值驾茴，有時候自己容易想當然的認為盼樟！
