爬楼梯

爬楼梯

递归解法

• 递归解法的关键在于要找到函数恒等式，即推导公式f(n)=f(n-1)+f(n-2)

class Solution {
public:
    int climbStairs(int n) 
    {
    //注意：这里终止条件有两个
    if(n==1)
    return 1;
    if(n==2)
    return 2;
    //3.本级递归干什么:计算当前层的爬法总数
    int ret=climbStairs(n-1)+climbStairs(n-2);
    //2.返回当前层n的爬法总数
    return ret;
    }
};

• 那么有什么办法可以让递归解法不超时呢？
• 记忆化递归
• 在上一种方法中，我们计算每一步的结果时出现了冗余。另一种思路是，我们可以把每一步的结果存储在 memo
• 数组之中，每当函数再次被调用，我们就直接从 memo 数组返回结果。
• 在 memo数组的帮助下，我们得到了一个修复的递归树，其大小减少到 nn 。

class Solution {
public:
    int climbStairs(int n)
    {
        int* ret = new int[n+1];
        return climb(0,ret, n);
    }
    //这里注意ret数组0号位置存放的是n阶楼梯总爬法的可能
    //数组最后一个元素是1阶楼梯爬法总数
    int climb(int i,int ret[],int n)
    {
        if (i> n)
        {
            return 0;
         }
        else if (i == n)
        {
            return 1;
        }
        else if (ret[i] > 0)
        {
            return ret[i];
        }
        else
        {
            return ret[i] = climb(i + 1, ret, n) + climb(i + 2, ret, n);
        }
    }
};

动态规划

• 本问题其实常规解法可以分成多个子问题，爬第n阶楼梯的方法数量，等于 2 部分之和
  1.爬上 n−1 阶楼梯的方法数量。因为再爬1阶就能到第n阶
  2.爬上 n−2 阶楼梯的方法数量，因为再爬2阶就能到第n阶
• 所以我们得到公式 dp[n] = dp[n-1] + dp[n-2]
• 同时需要初始化 dp[0]=1 和 dp[1]=1
• 时间复杂度：O(n)

class Solution {
public:
    int climbStairs(int n)
    {
        int* dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
};

官方提供的更高级版本的动态规划—滚动数组

class Solution {
public:
    int climbStairs(int n)
    {
        int p=0,q=0,r=1;
        for(int i=1;i<=n;i++)
        {
            p=q;
            q=r;
            r=p+q;
        }
        return r;
    }
};

• 此题还有矩阵快速幂解法和通项公式解法，有兴趣的可以去官方题解看看