题目:509. 斐波那契数 - 力扣（LeetCode）

思路:这题用动规:O(N)，如果是递归:O(2^N）直接超时了。

代码:

class Solution {
public:
    int fib(int n) {
        if(n <= 1)return n;
        vector<int>dp(n+1);//定义一个数组去存放
        dp[0] = 0, dp[1] = 1;
        for(int i = 2; i<= n; i++)
        {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

题目;70. 爬楼梯 - 力扣（LeetCode）

思路:爬楼梯的题目就类似于斐波那契数，注意这里不需要初始化dp[0]

代码:

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