关于爬楼梯算法分析

Q:

前段时间笔试，遇到了以前学的一个算法，大学时没认真想，只是记着怎么写，现在得空，总结一下这个问题的解法。题目如下：

有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一个算法，计算小孩有多少种上楼梯的方式。输入n，返回一个整数。

A:

老师当年说呦，这个题目可以用递归，求出n-1，n-2，n-3级台阶的总和，就是答案。但是为啥嘞，我来解释一哈;

1. 因为每次只能走1，2，3阶，所以，当一共5级台阶时，可以看成在走了4阶基础上再跨1阶 + 走了3阶基础上再跨2阶 + 走了2阶基础上再跨3阶。示例图如下👇：

   
   台阶排列图解.jpg

2. 因此，对于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，返回一个整数。

1. 由上例得：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)
   那么先按最简单递归法写，哈哈哈，原谅我比较懒，其他方法会后续再补充，也欢迎大家一起讨论~

2. 参照上例思路，我们可以在递归里分为两大部分，一部分是 steps > maxStep 时，参照f(s,m) = f(s-1) + f(s-2) + f(s-3) + ··· + f(s-m)进行累加。

3. 我们现在看 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;

4. 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]);

以上 <(￣︶￣)>