如果一个机器人 一次可以上 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. 解决问题（通常使用数组进行迭代求出最优解）
================================================================================================================