Leetcode.70.Climbing Stairs

题目

爬楼梯, 一共有n个阶梯, 每次可以爬1层或2层, 一共有多少种爬法.

Input: 2
Output: 2
Input: 3
Output: 3

思路1

递归, 将f(n)分为f(n+1)+f(n+2), 不采用缓存的情况下时间复杂度为2的n次方. 采用缓存情况下时间复杂度为O(n).

• 无缓存

  int recrutionClimbStairs(int start, int end) {
      if (start > end) {
        return 0;
      }   
      if (start == end) {
        return 1;
      }
  
      return recrutionClimbStairs(start + 1, end) + recrutionClimbStairs(start + 2, end);
  }
  int climbStairs(int n) {
      return recrutionClimbStairs(0, n) ;
  }
  

• 有缓存

  int recrutionClimbStairs(int start, int len, vector<int> &caches) {
    if (caches[len] > 0) {
        return caches[len];
    }
    cout << start << "->" << len << endl;
    if (0 > len) {
        return 0;
    } 
    if (1 == len) {
        return 1;
    } else if (2 == len) {
        return 2;
    }
    caches[len] = recrutionClimbStairs(start, len - 1, caches) + recrutionClimbStairs(start, len - 2, caches);
    return caches[len];
  }
  // 递归
  int climbStairs(int n) {
    vector<int> caches(n+1, 0); 
    return recrutionClimbStairs(0, n, caches) ;
  }
  

思路2

斐波那契函数, f(n) = f(n-1) + f(n-2).

int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }
  int first = 1;
  int second = 2;
  for (int i = 3; i <= n; i++) {
      int third = first + second;
      first = second;
      second = third;
  }
  return second;
}

总结

了解斐波那契数列, 在使用递归时优先使用缓存.