<b>第三章：動态規劃</b>
1、 分治算法和動态規劃算法都是通過對問題進行分解，通過對子問題的求解然後進行解重構，進而實作對原問題的求解。請指出這兩種算法在對問題進行分解時各自所遵循的原則。
答：分治算法對問題進行分解時所遵循的原則是将待求解問題分解為若幹個規模較小、互相獨立且與原問題相同的子問題（不包含公共的子問題）。
動态規劃對問題進行分解時所遵循的原則是将待求解問題分解為若幹個規模較小、互相關聯的與原問題類似的子問題（包含公共的子問題），采用記錄表的方法來儲存所有已解決問題的答案，而在需要的時候再找出已求得的答案，避免大量的重複計算。
2、 動态規劃算法的本質是什麼，請簡要闡述。
答：動态規劃的實質是<b>分治思想</b>和<b>解決備援</b>，動态規劃算法是将問題分解為更小的、相似的子問題，并存儲子問題的解而避免計算重複的子問題，以解決最優化問題的算法政策。
3、 如果一個問題可以利用動态規劃算法求解，那麼該問題應滿足什麼條件？
答：該問題具有最優子結構性質（一個問題的最優解包含其子問題的最優解）和無後效性(将各階段按照一定的次序排列好之後，對于某個給定的階段狀态，它以前各階段的狀态無法直接影響它未來的決策，而隻能通過目前的這個狀态).
4、動态規劃算法的基本思想是什麼？請簡述動态規劃算法主要設計步驟。
答：動态規劃算法的基本思想是将待求解問題分解成若幹個互相關聯的與原問題類似的子問題，求解這些子問題，并儲存子問題的答案，避免重複計算，然後從這些子問題的解得到原問題的解。
動态規劃算法主要設計步驟：
1）找出最優解的性質，并刻畫其結構特征；
2）遞歸地定義最優值；
3）以自底向上的方式計算出最優值；
4）根據計算最優值時得到的資訊，構造最優解；
5，什麼是備忘錄方法？它同動态規劃法相比主要不同點是什麼？請指出動态規劃法和備忘錄方法各自的适用範圍。(注：平常說的“動态規劃”是自底向上的動态規劃，“備忘錄方法”是自頂向下的動态規劃。)
答：備忘錄方法是動态規劃算法的變形，它通過分治思想對原問題進行分解，以存儲子問題的解的方式解決備援計算，并采用自頂向下的遞歸方式擷取問題的最終解。
與動态規劃算法的不同之處是動态規劃算法的遞歸方式是自底向上遞歸求解，而備忘錄方法的遞歸方式是自頂向下遞歸求解。
當一個問題的所有子問題都至少要解一次時，使用動态規劃算法。
當子問題空間中的部分子問題不需要求解時，使用備忘錄方法。
6，矩陣相乘算法目前最好的時間複雜度是多少？
答：目前矩陣乘法最好的時間複雜度是能做到O（n2.376）
7，分治法與動态規劃法之間的相同點是什麼？不同之處在哪些方面？
答：與分治法類似，動态規劃法 也是把問題一層一層地分解為規模逐漸減小的同類型的子問題。
動态規劃法與分治法的一個重要的不同點在于，用分治法分解後得到的子問題通常都是互相獨立的， 而用動态規劃法分解後得到的子問題很多都是重複的。是以，對重複出現的子問題，隻是在第一次遇到時才進行計算，然後把計算所得的結果儲存起來；當再次遇到該子問題時，就直接引用已儲存的結果，而不再重新求解。
例題：
1，
<a href="http://blog.51cto.com/attachment/201203/013128851.png" target="_blank"></a>
2，
<a href="http://blog.51cto.com/attachment/201203/013155657.png" target="_blank"></a>
3，動态0-1背包
public class SF_Beibao_0_1{
public static void main(String[]args){
int []v={1,2,3,4,5,6,7};
int []w={2,3,4,5,34,23,2};
int []b={2,3,4,1,2,3,5};
int c=45;
int d=36;
int [][][]m=new int[v.length][c+1][d+1];
knapsack(v,w,b,c,d,m);
System.out.println("輸出最優解："+m[1][c][d]);
}
public static void knapsack(int[]v,int[]w,int []b,int c,int d,int[][][]m){
int n=v.length-1;
int jMax=Math.min(w[n]-1,c);
int kMax=Math.min(b[n]-1,d);
for(int j=0;j<=jMax;j++)
for(int k=0;k<=kMax;k++)
m[n][j][k]=0;
for(int j=w[n];j<=c;j++)
for(int k=b[n];k<=d;k++)
m[n][j][k]=v[n];
for(int i=n-1;i>1;i--){
jMax=Math.min(w[i]-1,c);
kMax=Math.min(b[i]-1,d);
for(int j=0;j<=jMax;j++)
for(int k=0;k<=kMax;k++)
m[i][j][k]=m[i+1][j][k];
for(int j=w[i];j<=c;j++)
for(int k=b[i];k<=d;k++)
m[i][j][k]=Math.max(m[i+1][j][k],m[i+1][j-w[i]][k-b[i]]+v[i]);
}
m[1][c][d]=m[2][c][d];
if(c>=w[1]&&d>=b[1])m[1][c][d]=Math.max(m[1][c][d],m[2][c-w[1]][d-b[1]]+v[1]);
}
public static void trackback(int[][][]m,int[]b,int[]w,int c,int d,int[]x){
int n=w.length-1;
for(int i=1;i<n;i++)
if(m[i][c][d]==m[i+1][c][d])x[i]=0;
else {x[i]=1;c-=w[i];d-=b[i];}
x[n]=(m[n][c][d]>0)?1:0;
}
}
4，
<a href="http://blog.51cto.com/attachment/201203/013246399.png" target="_blank"></a>
本文轉自 夢朝思夕 51CTO部落格，原文連結:http://blog.51cto.com/qiangmzsx/802715
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)