一拭卿、動態(tài)規(guī)劃法
經(jīng)常會遇到復雜問題不能簡單地分解成幾個子問題杖狼，而會分解出一系列的子問題。簡單地采用把大問題分解成子問題颈畸，并綜合子問題的解導出大問題的解的方法，問題求解耗時會按問題規(guī)模呈冪級數(shù)增加没讲。為了節(jié)約重復求相同子問題的時間眯娱，引入一個數(shù)組，不管它們是否對最終解有用爬凑，把所有子問題的解存于該數(shù)組中徙缴，這就是動態(tài)規(guī)劃法所采用的基本方法。
二嘁信、問題：求兩字符序列的最長公共字符子序列（LCS）
問題描述：字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干個字符（可能一個也不去掉）后所形成的字符序列于样。令給定的字符序列X=“x0，x1潘靖，…穿剖，xm-1”，序列Y=“y0卦溢，y1糊余，…秀又，yk-1”是X的子序列，存在X的一個嚴格遞增下標序列<i0贬芥，i1吐辙，…，ik-1>蘸劈，使得對所有的j=0昏苏，1，…昵时，k-1捷雕，有xij=yj。例如壹甥，X=“ABCBDAB”救巷，Y=“BCDB”是X的一個子序列。
三句柠、分析
考慮最長公共子序列問題如何分解成子問題浦译，設A=“a0，a1溯职，…精盅，am-1”，B=“b0谜酒，b1叹俏，…，bm-1”僻族，并Z=“z0粘驰，z1，…述么，zk-1”為它們的最長公共子序列蝌数。不難證明有以下性質(zhì)：
（1） 如果am-1=bn-1，則zk-1=am-1=bn-1度秘，且“z0顶伞，z1，…剑梳，zk-2”是“a0唆貌，a1，…垢乙，am-2”和“b0挠锥，b1，…侨赡，bn-2”的一個最長公共子序列蓖租；
（2） 如果am-1!=bn-1粱侣，則若zk-1!=am-1，蘊涵“z0蓖宦，z1齐婴，…，zk-1”是“a0稠茂，a1柠偶，…，am-2”和“b0睬关，b1诱担，…，bn-1”的一個最長公共子序列电爹；
（3） 如果am-1!=bn-1蔫仙，則若zk-1!=bn-1，蘊涵“z0丐箩，z1摇邦，…，zk-1”是“a0屎勘，a1施籍，…，am-1”和“b0概漱，b1丑慎，…，bn-2”的一個最長公共子序列瓤摧。
這樣立哑，在找A和B的公共子序列時，如有am-1=bn-1姻灶，則進一步解決一個子問題，找“a0诈茧，a1产喉，…，am-2”和“b0敢会，b1曾沈，…，bm-2”的一個最長公共子序列鸥昏；如果am-1!=bn-1塞俱，則要解決兩個子問題，找出“a0吏垮，a1障涯，…罐旗，am-2”和“b0，b1唯蝶，…九秀，bn-1”的一個最長公共子序列和找出“a0，a1粘我，…鼓蜒，am-1”和“b0，b1征字，…都弹，bn-2”的一個最長公共子序列，再取兩者中較長者作為A和B的最長公共子序列匙姜。
四畅厢、求解
引進一個二維數(shù)組c[][]，用c[i][j]記錄X[i]與Y[j] 的LCS 的長度搁料，b[i][j]記錄c[i][j]是通過哪一個子問題的值求得的或详，以決定搜索的方向。
我們是自底向上進行遞推計算郭计，那么在計算c[i,j]之前霸琴，c[i-1][j-1]，c[i-1][j]與c[i][j-1]均已計算出來昭伸。此時我們根據(jù)X[i] = Y[j]還是X[i] != Y[j]梧乘，就可以計算出c[i][j]。
問題的遞歸式寫成：
example：
public class WDLCS {
public int findLCS(String A, String B) {
int n = A.length();
int m = B.length();
char[] a = A.toCharArray();
char[] b = B.toCharArray();
int[][] dp = new int[n][m];
for (int i = 0; i < n; i++) {//第一列
if (a[i] == b[0]) {
dp[i][0] = 1;
for (int j = i + 1; j < n; j++) {
dp[j][0] = 1;
}
break;
}
}
for (int i = 0; i < m; i++) {//第一行
if (a[0] == b[i]) {
dp[0][i] = 1;
for (int j = i + 1; j < m; j++) {
dp[0][j] = 1;
}
break;
}
}
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]);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(dp[i][j] + " ");
}
System.out.println();
}
return dp[n - 1][m - 1];
}
public static void main(String[] args) {
WDLCS lcs = new WDLCS();
//int findLCS = lcs.findLCS("object", "wdobject");
int findLCS = lcs.findLCS("object", "wobjedct");
System.out.println("最長子序列長度：" + findLCS);
}
}
