爬楼梯

---

题目描述

你在爬楼梯，需要n步才能爬到楼梯顶部

每次你只能向上爬1步或者2步。有多少种方法可以爬到楼梯顶部？

解题思路

写出1~5格楼梯的可能路径，分析可知应该是斐波那契序列。f(n)=f(n-1)+f(n-2)但是发现用递归的方式的代码，运行时间复杂度过高，没能通过。

为了解决递归造成的高时间复杂度，可以试着用循环的方式解决。

代码

class Solution
{
public:
    int climbStairs (int n)
    {
        if (n <= 2)
            return n;
        int temp = 0;
        int res = 2;
        int pre = 1;
        
        for (int i = 3; i <= n; i++)
        {
            temp = res;
            res = temp + pre;
            pre = temp;
        }
        return res;
    }
};

动态规划的方法，也类似上面这种方法，通过一个一维数组实现存储结果

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

参考链接：

https://www.nowcoder.com/questionTerminal/d679cfa563974385a3bef8cd854c73db?f=discussion