代码随想录算法训练营第三十八 |● 509. 斐波那契数 ● 70. 爬楼梯 ● 746. 使用最小花费爬楼梯

我在每一个算法开始之前都会去认真的看一下这个理论基础，或者说是算法的主要思想，可以直接看视频carl讲解的很清晰；其次还会大致看一下这一part中的题型及难度
动态规划理论基础讲解链接：https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

视频：https://www.bilibili.com/video/BV13Q4y197Wg

509. 斐波那契数

https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html
视频：https://www.bilibili.com/video/BV1f5411K7mo

class Solution {
public:
    int fib(int n) {
        if(n<=1) return n;
        //dp[i] 第i个斐波那契数值为dp[i]
        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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

70. 爬楼梯

https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html
视频：https://www.bilibili.com/video/BV17h411h7UH

class Solution {
public:
    int climbStairs(int n) {
        //dp[i]表示  爬到第i层楼梯，有dp[i]种方法
        //上i-1层楼梯，有dp[i - 1]种方法，i层就加一
        //dp[i] = dp[i-1]+dp[i-2]
        if(n<=1) return n;
        //希望从i=1开始
        vector<int> dp(n+1);    //犯了个低级错误定义成了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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

746. 使用最小花费爬楼梯

https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html
视频讲解：https://www.bilibili.com/video/BV16G411c7yZ

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size()+1);
        dp[0] = 0;
        dp[1] = 0;
        for(int i=2; i<=cost.size();i++) {
            dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12