Q:
前段时间笔试，遇到了以前学的一个算法，大学时没认真想，只是记着怎么写，现在得空，总结一下这个问题的解法。题目如下：
有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一个算法，计算小孩有多少种上楼梯的方式。输入n，返回一个整数。
A:
老师当年说呦，这个题目可以用递归，求出n-1，n-2，n-3级台阶的总和，就是答案。但是为啥嘞，我来解释一哈;
-
因为每次只能走1，2，3阶，所以，当一共5级台阶时，可以看成在走了4阶基础上再跨1阶 + 走了3阶基础上再跨2阶 + 走了2阶基础上再跨3阶。示例图如下👇：
台阶排列图解.jpg
- 因此，对于n阶台阶，可以看成走了n-1阶基础上再跨1阶 + 走了n-2阶基础上再跨2阶 + 走了n-3阶基础上再跨3阶。
即：f(n): f(n-1) + f(n-2) + f(n-3)
代码如下：（OC，递归）
- (int)countBySteps:(int)steps
{
int count = 0;
if (steps == 0) {
return 0;
}
if (steps == 1) {
return 1;
}else if (steps == 2){
return 2;
}else if (steps == 3){
return 4;
}else if (steps > 3){
return [self countBySteps:steps-1] + [self countBySteps:steps-2] + [self countBySteps:steps-3];
}
return count;
}
测试：
int stepNum = 15;
NSLog(@"A %d级台阶，共有上楼方式%d种",stepNum,[self countBySteps:stepNum]);
下面讨论，一次可以跨不止3级的情况，题目改成如下：
这小屁孩的老师作业留少了，闲着没事爬楼梯，楼梯有s阶台阶(steps)，小孩一次可以上m阶（maxStep）。计算小孩有多少种上楼梯的方式。输入s,m，返回一个整数。
由上例得：f(n) = f(n-1) + f(n-2) + f(n-3)，
那么当最多跨m阶时为：f(s,m) = f(s-1) + f(s-2) + f(s-3) + ··· + f(s-m)
那么先按最简单递归法写，哈哈哈，原谅我比较懒，其他方法会后续再补充，也欢迎大家一起讨论~参照上例思路，我们可以在递归里分为两大部分，一部分是 steps > maxStep 时，参照f(s,m) = f(s-1) + f(s-2) + f(s-3) + ··· + f(s-m)进行累加。
-
我们现在看 steps <= maxStep 时，怎么给出类似上例里 f(2)，f(3)的返回值。其实，上例中的f(3)，就是台阶一共3级，最大可以跨三步的值，即f(2) 就是 f(2,2)，f(3)就是f(3,3)，你好好想想是不是这个理儿~
所以，f(m,m)的图解如下👇：
f(m,m)图解.jpg
根据以上得出：
steps > maxStep 时，f(s,m) = f(s-1) + f(s-2) + f(s-3) + ··· + f(s-m);
steps <= maxStep时，f(m,m) = f(m,m-1) +1;
steps = 1时，return 1;
steps = 0时，return 0;
- so，算法如下：
- (int)countBySteps:(int)steps MaxStep:(int)maxStep
{
int count = 0;
if (steps == 0) {
return count;
}
if (steps == 1) {
count = 1;
}else{
if (steps > maxStep) {
for (int i = 1; i <= maxStep; i++) {
count += [self countBySteps:(steps - i) MaxStep:maxStep];
}
}else{
count = [self countBySteps:steps MaxStep:(steps - 1)] + 1;
}
}
return count;
}
测试👇：
int stepNum = 15;
int maxStep = 3;
NSLog(@"A %d级台阶，共有上楼方式%d种",stepNum,[self countBySteps:stepNum]);
NSLog(@"B %d级台阶，共有上楼方式%d种",stepNum,[self countBySteps:stepNum MaxStep:maxStep]);
