爬楼梯

斐波那契数列

斐波那契数列的数学形式就是递归的，写成代码就是这样：

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

这个算法的时间复杂度为 $O(2^n)$

带备忘录的递归解法

明确了问题，其实就已经把问题解决了一半。即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。

int fib(int N) {
    if (N < 1) return 0;
    vector<int> memo(N + 1, 0);// 备忘录全初始化为 0
    return helper(memo, N);// 初始化最简情况
}
 
int helper(vector<int>& memo, int n) {
    if (n == 1 || n == 2) return 1;// base case 
    if (memo[n] != 0) return memo[n];// 已经计算过
    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    return memo[n];
}

对题目进行分析

- 只有1个台阶的时候    总共有1种走法
- 只有2个台阶的时候    总共有2种走法
- 只有3个台阶的时候    总共有3种走法
- 只有4个台阶的时候    总共有5种走法
- 只有5个台阶的时候    总共有8种走法
- ......

此时我们发现规律：f(n)=f(n-1)+f(n-2),这个递推公式正符合斐波那契数列

class Solution {
public:
    int climbStairs(int n) {
        if(n<1) return 0;
        vector<int> memo(n+1,0);
        return helpf(memo,n);
    }
    int helpf(vector<int> &memo,int n){
        if(n<4) return n;
        if (memo[n] != 0) return memo[n];
        memo[n] = helpf(memo,n-1)+helpf(memo,n-2);
        return memo[n];
    }

};

class Solution {
public:
    int climbStairs(int n) {
        if(n==0||n==1)
        return 1;
        int a=1,b=2;
        for(int i=3;i<=n;i++)
        {
            int c=a+b;
            a=b;
            b=c;
        }
        return b;
    }
};