1，假设有n个台阶的楼梯，一个人要上这个楼梯，他每次可以走1个台阶或者2个台阶，问走上这个楼梯的走法总共有多少种？
解答：这个题目可以从最简单的办法逐步掌握其规律，比如走上1个台阶总共只有1种走法，而走上2个台阶有两种走法（一种直接走2步，一种走2个一步），我们知道要走上第i个台阶，要么是从第i-1个台阶走一小步到的，要么是从第i-2个台阶走1大步。用F(i)表示走上第i个台阶的走法总数，那么F(1)=1，F(2)=2，那么F(i)是依赖于F(i-1)和F(i-2)的，其中 2<i<=n, 我们很容易知道 F(i)=F(i-1)+F(i-2)。也就是说我们最终问题的解为F(n)=F(n-1)+F(n-2)，F(1)=1，F(2)=2. 了解斐波那契数列的人就知道这明显就是一个斐波那契数列。
可以通过方程递归的求解问题：
int Step(int n)//递归 { if(n==1) return 1; else if (n==2) return 2; else return Step(n-1)+Step(n-2); }
这个过程的时间复杂度为O(2^n)，我们可以用循环递推来改变这个时间代价：
int func(int n)//时间复杂度是O(n) { int *a = new int[n]; a[0] = 1; a[1] = 2; for (int i = 2;i<n;i++) { a[i] = a[i - 1] + a[i - 2]; } int res = a[n - 1]; delete[] a; return res; }
对以上俩函数进行测试对比：
#include<iostream> #include<time.h> using namespace std; int step(int n);//递归 int func(int n);//改进 int main(void) { clock_t start, finish; double t1,t2; int ditui,diaoyong; start = clock(); diaoyong= step(30);//假设30台阶 cout << diaoyong << endl; finish = clock(); t1 = (double)(finish - start) / CLOCKS_PER_SEC*1000000; cout <<"函数循环调用使用了"<< t1 << " 微秒" << endl; start = clock(); ditui = func(30); cout << ditui << endl; finish = clock(); t2= (double)(finish - start) / CLOCKS_PER_SEC * 1000000; cout <<"数组递推使用了"<< t2 << " 微秒" << endl; return 0; }
测试结果对比
2.一个人上台阶可以一次上1个，2个，或者3个，问这个人上n层的台阶，总共有几种走法？
同样地我们也可以使用上述方法：
//函数递归调用 int step(int n) { if (n == 1) return 1; else if (n == 2) return 2; else if (n == 3) return 4; else return step(n - 1) + step(n - 2)+ step(n - 3); } //数组循环 int func(int n) { int *a = new int[n]; a[0] = 1; a[1] = 2; a[2] = 4; for (int i = 3;i<n;i++) { a[i] = a[i - 1] + a[i - 2]+ a[i - 3]; } int res = a[n - 1]; delete[] a; return res; }