【代码随想录_Day27】509 斐波那契数 70 爬楼梯 746 使用最小花费爬楼梯

以下是今日份的总结

509 斐波那契数
70 爬楼梯
746 使用最小花费爬楼梯

今天的题目难度不高，掌握技巧了就会很简单，尽量还是写一些简洁代码 ^ _ ^

斐波那契数

思路：

1.确定dp数组以及下标的含义
------ dp[i]的定义为：第i个数的斐波那契数值是dp[i]
2.确定递推公式
------dp[i] = dp[i - 1] + dp[i - 2];
3.dp数组如何初始化
------dp[0] = 0;
------dp[1] = 1;
4.确定遍历顺序
------从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
5.举例推导dp数组
------当N为10的时候, 0 1 1 2 3 5 8 13 21 34 55

值得注意的是

只需要维护两个数值就可以了，不需要记录整个序列。

    int fib(int n) {
        vector<int> dp(n+1);
        if(n<2) return n;
        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

    int fib(int n) {
        if(n<2) return n;
        int dp[2];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i<=n;i++){
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum ; 
        }
        return dp[1];
    }
1
2
3
4
5
6
7
8
9
10
11
12

爬楼梯

思路：

和上一题表现形式差不多
1.确定dp数组以及下标的含义
------ dp[i]： 爬到第i层楼梯，有dp[i]种方法
_
2.确定递推公式
------首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。
------还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。
------dp[i] = dp[i - 1] + dp[i - 2];
_
3.dp数组如何初始化
------dp[0] = 0;//这一步实际上并不重要
------dp[1] = 1;
------dp[2] = 2;
_
4.确定遍历顺序
------从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
_
5.举例推导dp数组
------当N为10的时候, 0 1 2 3 5 8 13 21 34 55
界不揍是斐波那契数列嘛！！

值得注意的是

和上题一样

    int climbStairs(int n) {
        if(n<2) return n;
        vector<int>dp(n+1);
        dp[0] = 0;
        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

使用最小花费爬楼梯

思路：

1.确定dp数组以及下标的含义
------ dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。
2.确定递推公式
------可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。
------dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
------dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。
------那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢？
------一定是选最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
3.dp数组如何初始化
------到达 第 0 个台阶是不花费的，但从 第0 个台阶 往上跳的话，需要花费 cost[0]
------又因为题目允许上一层或者两层，所以
------dp[0] = 0;
------dp[1] = 0;
4.确定遍历顺序
------dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
5.举例推导dp数组
------cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 楼顶
------下标 0 1 2 3 4 5 6 7 8 9 10
------dp = [0,0,1,2,2,3,3,4,4,5,6]

值得注意的是

和上题一样

    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

写在最后

----OK，今日份的博客就写到这里，这一期的动态规划好巧妙，明天继续加油！！！
—还没看下期的题，但是我的栈还有一节没写；
–追上时间进度了！！（笑
-该丢的都丢掉，然后闪亮的飞速奔向远方。