當(dāng)遇到復(fù)雜問(wèn)題時(shí)我們經(jīng)常會(huì)通過(guò)遞歸的方式將大事化小浓瞪，小事化了。但是有時(shí)候?qū)?fù)雜問(wèn)題簡(jiǎn)單地分解成幾個(gè)子問(wèn)題，問(wèn)題求解耗時(shí)會(huì)按問(wèn)題規(guī)模呈冪級(jí)數(shù)增加褐健。這時(shí)候?yàn)榱斯?jié)約重復(fù)求相同子問(wèn)題的時(shí)間，引入一個(gè)數(shù)組(或臨時(shí)變量)澜汤，不管它們是否對(duì)最終解有用蚜迅，把所有子問(wèn)題的解存于該數(shù)組(或臨時(shí)變量)中，這就是動(dòng)態(tài)規(guī)劃的基本思想俊抵。
1.Fibonacci數(shù)列
該數(shù)列的遞歸形式如下谁不，即從每二項(xiàng)開(kāi)始每一項(xiàng)等于前兩項(xiàng)之和：
根據(jù)定義可以用遞歸方式寫(xiě)出如下代碼：
public int fib(int n) { // 計(jì)算Fibonacci數(shù)列的第n項(xiàng)（二分遞歸版）：O(2^n)
return (2 > n) ? n // 若到達(dá)遞歸基，直接取值
: fib(n - 1) + fib(n - 2); // 否則徽诲，遞歸計(jì)算前兩項(xiàng)刹帕，其和即為正解
}
遞規(guī)版本的時(shí)間復(fù)雜度將呈指數(shù)級(jí)別，明顯不能很好的解決問(wèn)題谎替，現(xiàn)通過(guò)犧牲空間復(fù)雜度偷溺，利用動(dòng)態(tài)規(guī)劃的思想將時(shí)間復(fù)雜度控制降低到O(n).
public static int fib1(int n) { // 計(jì)算Fibonacci數(shù)列的第n項(xiàng)（動(dòng)態(tài)規(guī)劃版）：O(n)
if(n < 2) return n;
int a = 0;//第一個(gè)值
int b = 1;//第二個(gè)值
int tmp = 0;//輔助變量
for(int i = 2;i <= n;i++){
tmp = a + b;
a = b;
b = tmp;
}
return tmp;
}
2.爬樓梯
問(wèn)題描述：有一座高度為n級(jí)的樓梯，從下往上走钱贯，每跨一步只能向上1級(jí)或者2級(jí)臺(tái)階挫掏，求出一共有多少種走法。
分析：因?yàn)槊?步只能走1級(jí)或者2級(jí)秩命，所以走到第n級(jí)的前一步有且只有兩種情況砍濒，第一種情況是從第n - 1級(jí)走1級(jí)淋肾，第二種情況是從第n - 2級(jí)走2級(jí)。由此我們就可以得到此問(wèn)題的遞歸公式：
F(1) = 1;
F(2) = 2;
F(n) = F(n - 1) + F(n - 2);
看到這里爸邢，相信聰明的你很快就反映過(guò)來(lái)了這不就是上面的Fibonacci數(shù)列問(wèn)題嘛(注意：起始值不同)樊卓，下面直接給出動(dòng)態(tài)規(guī)劃思想的代碼實(shí)現(xiàn):
public static int getNum(int n) {
if(n <= 2) return n;
int a = 1;//只有1級(jí)臺(tái)階的情況
int b = 2;//有2級(jí)臺(tái)階的情況
int tmp = 0;//輔助變量
for(int i = 3;i <= n;i++){
tmp = a + b;
a = b;
b = tmp;
}
return tmp;
}
3.最長(zhǎng)公共子序列
有了上面兩個(gè)動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)的熱身，下面看一個(gè)復(fù)雜點(diǎn)的問(wèn)題杠河，首先看一下兩個(gè)定義：
子序列(Sequence)：由序列中若干字符碌尔，按原相對(duì)次序構(gòu)成。
最長(zhǎng)公共子序列(Longest Common Subsequence）:兩個(gè)序列公共子序列中的最長(zhǎng)者券敌，下面簡(jiǎn)稱(chēng)LCS,可能出現(xiàn)下面兩種比較復(fù)雜的情況：
1).可能有多個(gè)
2).可能有歧義
現(xiàn)用遞歸的思想分析如下：
對(duì)于序列A[0,n]和B[0,m]唾戚，LCS(A,B)無(wú)非三種情況：
- 若n = - 1或 m = - 1，則取作空序列("")
- 若A[n] = ‘X' = B[m],則取作LCS(A[0,n), B[0,m)) + 'X',示意圖如下：
-
若A[n] != B[m],則在LCS(A[0,n], B[0,m))與LCS(A[0,n), B[0,m])中取更長(zhǎng)者
示意圖如下：
如下圖所示待诅，展示了“EDUCATIONAL”和“ADVANTAGE”通過(guò)遞歸思想求最長(zhǎng)公共子序列的過(guò)程叹坦。
代碼實(shí)現(xiàn)如下：
/**
* 遞歸方式實(shí)現(xiàn)求兩個(gè)字符串最長(zhǎng)公共字序列的長(zhǎng)度
* @param str1 第一個(gè)字符串
* @param m 第一個(gè)字符串需要比較的長(zhǎng)度
* @param str2 第二個(gè)字符串
* @param n 第一個(gè)字符串需要比較的長(zhǎng)度
* @return
*/
public static int lcs(String str1,int m,String str2,int n){
if(m == 0 || n == 0) return 0;//如果其中有一個(gè)元素為空則返回0
if(str1.charAt(m - 1) == str2.charAt(n - 1))
return lcs(str1,m - 1,str2,n - 1) + 1;//如果需要比較的兩個(gè)字符串最后一個(gè)字符相同則將問(wèn)題縮小
//剩下的情況則兩個(gè)字符串的最后一個(gè)字符不相等，取兩種情況中的最大值
return getMax(lcs(str1,m - 1,str2,n),lcs(str1,m,str2,n - 1));
}
可以看出如果最后一個(gè)字符不相等卑雁，反而會(huì)將問(wèn)題的規(guī)模擴(kuò)大募书，當(dāng)m與n大小接近時(shí)，時(shí)間復(fù)雜度也呈指數(shù)級(jí)別测蹲。下面將考慮通過(guò)動(dòng)態(tài)規(guī)劃的思想來(lái)實(shí)現(xiàn)：
構(gòu)造一個(gè)二維輔助數(shù)組莹捡，從上往下依次計(jì)算，如下圖所示：
代碼實(shí)現(xiàn)如下：
/**
* 非遞歸方式實(shí)現(xiàn)求兩個(gè)字符串最長(zhǎng)公共字序列的長(zhǎng)度
* @param str1 第一個(gè)字符串
* @param m 第一個(gè)字符串需要比較的長(zhǎng)度
* @param str2 第二個(gè)字符串
* @param n 第一個(gè)字符串需要比較的長(zhǎng)度
* @return
*/
public static int lcs1(String str1,int m,String str2,int n){
if(m == 0 || n == 0) return 0;
//構(gòu)建一個(gè)m + 1行 n + 1列的輔助二維數(shù)組,里面的元素初始值都為0
int[][] arr = new int[m + 1][n + 1];
//依次求二維數(shù)組中的值
for(int i = 1;i <= m;i ++){
for(int j = 1;j <= n; j ++){
//當(dāng)最后一個(gè)字符相等時(shí)等于左上角的元素加1
if(str1.charAt(i - 1) == str2.charAt(j - 1)) arr[i][j] = arr[i - 1][j - 1] + 1;
//不相等時(shí)取緊鄰左邊元素和上邊元素者的大者
else arr[i][j] = getMax(arr[i - 1][j],arr[i][j - 1]);
}
}
return arr[m][n];//二維數(shù)組右下角的元素即我們需要的值
}
總結(jié)：動(dòng)態(tài)規(guī)劃的思想通過(guò)犧牲空間復(fù)雜度的方式來(lái)大大減小時(shí)間復(fù)雜度扣甲，將自頂而下的計(jì)算方式改為自底而上篮赢，把已計(jì)算過(guò)的實(shí)例結(jié)果制表備查，從而取得非常顯著的效果琉挖。
