如果一個機器人 一次可以上 1 級台階，也可以一次上 2 級台階。求機器人走一個 n 級台階總共有多少種走法
先試着用分治法嘗試下
分治法核心思想： 從上往下分析問題，大問題可以分解為子問題，子問題中還有更小的子問題
比如總共有 5 級台階,求有多少種走法；由于機器人一次可以走兩級台階，也可以走一級台階，是以我們可以分 成兩個情況
- 機器人最後一次走了兩級台階，問題變成了“走上一個 3 級台階，有多少種走法？”
- 機器人最後一步走了一級台階，問題變成了“走一個 4 級台階，有多少種走法？”
我們将求 n 級台階的共有多少種走法用 f(n) 來表示，則 f(n) = f(n-1) + f(n-2);
由上可得 f(5) = f(4) + f(3);
f(4) = f(3) + f(2);
f(3) = f(2) + f(1);
邊界情況分析
走一步台階時，隻有一種走法，是以 f(1)=1
走兩步台階時，有兩種走法，直接走 2 個台階，分兩次每次走 1 個台階，是以 f(2)=2
走兩個台階以上可以分解成上面的情況
這符合我們講解的分治法的思想： 分而治之
代碼實作
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 /*遞歸實作機器人台階走法統計
5 參數:
6 n - 台階個數
7 傳回: 上台階總的走法
8 */
9
10 int WalkCout(int n)
11 {
12 if(n<0) return 0;
13 if(n==1) return 1; //一級台階，一種走法
14 else if(n==2) return 2; //二級台階，兩種走法
15 else
16 { //n 級台階， n-1 個台階走法 + n-2 個台階的走法
17 return WalkCout(n-1) + WalkCout(n-2);
18 }
19 }
20
21 int main(void)
22 {
23 for(int i=1; i<=6; i++)
24 {
25 printf("%d 台階共有 %d 種走法\n", i, WalkCout(i));
26 }
27
28 system("pause");
29 return 0;
30 } 但是上面的代碼中存在很多重複的計算。
比如: f(5) = f(4) + f(3)
計算分成兩個分支：
f(4) = f(3)+f(2) = f(2) + f(1) + f(2);
f(3) = f(2) + f(1) ;
上面紅色陰影的部分就是重複計算的一部分！
規避重複計算方法：
其實我們可以從下向上分析推斷問題。
f(1) = 1
f(2) = 2
f(3) = f(1) + f(2) = 3
f(4) = f(3) + f(2) = 3 + 2 = 5
f(5) = f(4) + f(3) = 5 + 3 = 8
。。。依次類推 。。。
實際求解過程
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 int WalkCount2(int n)
5 {
6 int ret = 0;
7
8 //無意義的情況
9 if(n <= 0)
10 return 0;
11
12 if(n == 1)
13 return 1;
14
15 if(n == 2)
16 return 2;
17
18 //數組用于存儲走 n 個台階的走法數
19 int* value = new int[n + 1];
20 value[0] = 0;
21 value[1] = 1;
22 value[2] = 2;
23 for(int i = 3; i <= n; i++)
24 {
25 value[i] = value[i - 1] + value[i - 2];
26 }
27
28 ret = value[n];
29 delete value;
30 return ret;
31 }
32
33 int main(void)
34 {
35 for(int i=1; i<=6; i++)
36 {
37 printf("%d 台階共有 %d 種走法\n", i, WalkCount2(i));
38 }
39
40 system("pause");
41 return 0;
42 } 這就是動态規劃法 !
動态規劃也是一種分治思想，但與分治算法不同的是，分治算法是把原問題分解為若幹子問題， 自頂向下，求解各子問題，合并子問題的解進而得到原問題的解。動态規劃也是自頂向下把原問 題分解為若幹子問題，不同的是，然後自底向上，先求解最小的子問題，把結果存儲在表格中， 在求解大的子問題時，直接從表格中查詢小的子問題的解，避免重複計算，進而提高算法效率。
什麼時候要用動态規劃？
如果要求一個問題的最優解（通常是最大值或者最小值），而且該問題能夠分解成若幹個子問題， 并且小問題之間也存在重疊的子問題，則考慮采用動态規劃。
怎麼使用動态規劃？
五步曲解決：
1. 判題題意是否為找出一個問題的最優解
2. 從上往下分析問題，大問題可以分解為子問題，子問題中還有更小的子問題
3. 從下往上分析問題 ，找出這些問題之間的關聯（狀态轉移方程）
4. 讨論底層的邊界問題
5. 解決問題（通常使用數組進行疊代求出最優解）
================================================================================================================