描述

有n阶楼梯，每次可以上一阶或者两阶楼梯，一共有多少种方法走完这些楼梯。

分析

设f(n)表示走第n阶楼梯的不同方法数，为了走到第n阶楼梯，共有两种方法：

• 从第n-1阶向上走一步；
• 从第n-2阶向上走两步；

因此，有 f(n) = f(n-1) + f(n-2)，这是一个斐波那契数列。

有几种方法进行计算：

1. 递归，递归比较慢，终止条件：
   • n == 1，返回1
   • n == 2，返回2
2. 迭代；
3. 使用斐波那契数列的通项公式；

实现

• 递归

  int climbingStairs00(int n)
  {
      if (n==1) {
          return 1;
      }
      if (n == 2) {
          return 2;
      }
      
      return climbingStairs00(n-1) + climbingStairs00(n-2);
  }
  

• 迭代

  int climbingStairs01(int n)
  {
      int cnt = 0;
      int prev = 0;
      int cur = 1;
      
      for(int i=1; i<=n; i++) {
          cnt = prev + cur;
          prev = cur;
          cur = cnt;
      }
      
      return cnt;
  }