假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

  1. 输入： 3
  2. 输出： 3
  3. 解释： 有三种方法可以爬到楼顶。
  4. 1.  1 阶 + 1 阶 + 1 阶
  5. 2.  1 阶 + 2 阶
  6. 3.  2 阶 + 1 阶

c plus

该题本质上是求斐波拉契数列。

  • 递归

    1. class Solution {
    2. public:
    3.   int climbStairs(int n) {
    4.       if (n <= 2) return n;
    5.       return climbStairs(n - 1) + climbStairs(n - 2);
    6.   }
    7. };
    8. //以上做法是傻递归的形式，会有很多重复性的计算，浪费大量的时间

  • 优化递归
    将上一种做法中重复计算的数据保存到数组，供下次直接使用

    1. class Solution {
    2. public:
    3.   int climbStairs(int n) {
    4.       if (n <= 2) return n;
    5.       vector<int> res(n, 0);
    6.       return f(n - 1) + f(n - 2);
    7.   }
    8.   int f(int n, vector<int>& res) {
    9.       if (n <= 2) return n;
    10.       if (res[n] != 0) return res[n];
    11.       return res[n] = f(n - 1) + f(n - 2);
    12.   }
    13. };

  • 迭代
    类似于递归中保存计算过的数据。

    1. class Solution {
    2. public:
    3.   int climbStairs(int n) {
    4.       if (n <= 2) return n;
    5.       vector<int> res(n + 1, 0);
    6.       res[1] = 1;
    7.       res[2] = 2;
    8.       for (int i = 3; i < n + 1; ++i) {
    9.           res[i] = res[i - 1] + res[i -2];
    10.       }
    11.       return res[n];
    12.   }
    13. };

  • 动态规划

本题为最简单的动态规划题目

  1. class Solution {
  2. public: 
  3.     int climbStairs(int n) {
  4.         if (n <= 2)    return n;
  5.         int a = 1;
  6.         int b = 2;
  7.         int tmp = 0;
  8.         for (int i = 3; i <= n; i++) {
  9.             tmp = a + b;
  10.             a = b;
  11.             b = tmp;
  12.         }  
  13.         return tmp;
  14.     }
  15. };