Chapter2: 时间复杂度分析、递归、查找与排序
9. 解题实战：小白上楼梯
题目
小白正在上楼梯，楼梯有n阶台阶，小白一次一次可以上1阶，2阶或3阶，实现一个方法，计算小白有多少种走完楼梯的方式。
算法
递归的解题思路：
-
找重复
因为一次可以上1阶，2阶或3阶，要计算到达n阶的方式，为到达n-1,n-2,n-3阶的方式之和
-
到达n-1阶之后，只有一种方式到达n阶，即跨1步
-
到达n-2阶之后，也只有一种方式到达n阶，即跨2步；跨1步到达n-1阶，再跨一步到达n阶这种方式实际上已经被包含在第1种情况里了
-
到达n-2阶之后，只有一种方式到达n阶，即跨3步
-
-
找变化
到达n阶的方式为到达n-1阶，n-2阶，n-3阶的方式之和
到达n-1阶的方式为到达n-2,n-3,n-4阶的方式之和
....
-
找出口
n=0时，只有1种
n=1时，只有1种
n=2时，有2种
所以设计算法如下
int f(int n){
if(n==0)
return 1;
if(n==1)
return 1;
if(n==2)
return 2;
return f(n-1)+f(n-2)+f(n-3);
}
网友评论