Studying-代码随想录训练营day33| 动态规划理论基础、509.斐波那契函数、70.爬楼梯、746.使用最小花费爬楼梯

发布于:2024-07-11 ⋅ 阅读:(26) ⋅ 点赞:(0)

第33天,动态规划开始,新的算法💪(ง •_•)ง,编程语言:C++

目录

动态规划理论基础

动态规划的解题步骤

动态规划包含的问题

动态规划如何debug

509.斐波那契函数

70.爬楼梯 

746.使用最小花费爬楼梯

总结 


动态规划理论基础

文档讲解:代码随想录动态规划理论基础

动态规划(Dynamic Programming),简称DP,通常用以解决某一问题有很多子问题的情况。

动态规划中每一个状态一定是由上一个状态推导出来的,这一点区别于贪心,贪心没有状态推导,而是从局部直接选出最优。

以背包问题为例,有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大?

在动态规划中dp[j]是由dp[j-weight[i]]推导出来的,然后取max(dp[j], dp[j - weight[i]] + value[i])。而贪心则是每次拿物品选一个最大的或者最小的就完事了,和上一个状态没有关系。所以贪心是解决不了动态规划的问题的。

动态规划的解题步骤

动态规划中,最重要的一个部分是状态转移公式,也即递推公式。但找到递推公式也只是一方面,我们在解题的时候,还需要构造dp数组,我们还需要确定dp数组中下标表示的含义,这样才能够有助于我们真正理解题目。

对于动态规划问题,我们可以把解题步骤拆解为如下五步:

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组(打印dp数组)

解题过程中,依据上述5步进行。注意对dp数组的初始化,是在确定递推公式后的,因为有些初始化是要依据递推公式进行的。

动态规划包含的问题

动态规划一般包含的问题有:

  • 基础题目
  • 背包问题
  • 打家劫舍
  • 股票问题
  • 子序列问题

动态规划是一个很大的领域,对于后面的每一种问题,还需要进行单独的讲解。

动态规划如何debug

我们在解动态规划问题时,如果出现无法通过的时候,一定不要慌张,代码出现问题是很正常的。我们最重要的是不能让代码对我们而言是黑盒状态,就是我们都不确定它的运行顺序和结果。

最好的debug方式,就是把dp数组打印出来,看看结果究竟是不是按照自己思路推导的,又是哪一个部分出了错误。

同时做动规的题目,写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍,心中有数,确定最后推出的是想要的结果

在对动态规划问题进行debug时,我们一定要牢记三个问题:

  • 这道题目我举例推导状态转移公式了么?
  • 我打印dp数组的日志了么?
  • 打印出来了dp数组和我想的一样么?

牢记上述三个问题,基本就能够解决动态规划解题过程中遇到的问题。 


509.斐波那契函数

文档讲解:代码随想录斐波那契函数

视频讲解:手撕斐波那契函数

题目:

学习:本题是非常经典的数学题目之一,也是标准的动态规划题目。递推公式在题干中就已经给了我们,剩下的就是我们依照动规五部曲,逐步进行。

1.确定dp数组以及下标的含义:在这里我们可以定义一个vector型的dp数组,dp[i]定义为第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]的,因此遍历顺序一定要从前往后进行遍历。

5.举例推导dp数组:我可以依照我们上述构造的dp数组和递推关系,当n = 10时,dp数组应该为:0,1,1,2,3,5,8,13,21,34,55。如果发现结果不对,我们也可以通过打印dp数组来查看问题出在哪。

代码:

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:
    int fib(int n) {
        //动态规划,使用dp数组,存储斐波那契数列数值
        if(n < 2) return n; //0,1单独处理
        vector<int> dp(n + 1); //从0-N,dp(n)表示第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];
    }
};

代码:对于本题来说,实际上也可以不适用dp数组,我们只需要维护两个值就可以了

//时间复杂度O(n)
//空间复杂度O(1)
class Solution {
public:
    int fib(int n) {
        //动态规划,不使用dp数值,只找到第n个值
        if(n < 2) return n;
        int dp0 = 0;
        int dp1 = 1;
        int sum;
        for(int i = 2; i <= n; i++) {
            sum = dp0 + dp1;
            dp0 = dp1;
            dp1 = sum;
        }
        return dp1;
    }
};

代码:本题还可以使用递推公式进行,代码极度简便,但并不好想。

//时间复杂度O(2^n)
//空间复杂度O(n)
class Solution {
public:
    int fib(int n) {
        //递归法,非常恐怖
        if(n < 2) return n;
        else return fib(n - 1) + fib(n - 2);
    }
};

70.爬楼梯 

文档讲解:代码随想录爬楼梯

视频讲解:手撕爬楼梯

题目:

学习:本题实际上是斐波那契数的变种,递推公式都是一样的。这也可见动态规划问题能够想出递推公式确认是十分重要的。

对于本题来说,由于一次可以爬1或2个台阶,因此对于第3层台阶来说,可以从第一层爬2层台阶到达,也可以从第二层爬1层台阶到达。而到达第一层和第二层的种类分别是dp[1]和dp[2]因此,到达第三层的种类就为dp[1]+dp[2],之后的第四层也是如此,能够通过从第二层爬2阶到达,也能够通过从第三层爬1阶到达……

最后就能够得到同样的递推公式dp[n] = dp[n - 1] + dp[n - 2]。但要注意本题中与斐波那契数不同的式dp[0]在本题中是没有意义的,虽然我们给dp[0]赋值为1(因为dp[2]=2)也能够解决问题,但是dp[0]是没有实际意义的,因此本题更推荐给dp[1]和dp[2]进行初始化。

代码:

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:
    int climbStairs(int n) {
        //动态规划
        //1.确定dp数组以及下标的含义
        vector<int> dp(n + 1); //dp(n)表示爬n阶的方法
        //2.确定递归条件:dp(n) = dp(n - 1) + dp(n - 2);
        //3.dp数组初始化,因为dp(0)是没有意义的,且n也不会等于0,因此不需要初始化0
        if(n <= 1) return n;
        dp[1] = 1;
        dp[2] = 2;
        //4.确定遍历顺序
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            //5.举例推导dp数组(打印dp数组)
            //cout << dp[i] << endl;
        }
        return dp[n];
    }
};

746.使用最小花费爬楼梯

文档讲解:代码随想录使用最小花费爬楼梯

视频讲解:手撕使用最小花费爬楼梯

题目:

学习:本题我们需要注意题干中的两个点:1.cost[i],是从i个台阶向上爬需要支付的费用,也就是我们只有向上爬了,才需要支付费用,我们站在i台阶上,是不需要支付cost[i]的。2.到达楼梯顶部不是指第最后的下标(cost.size() - 1)个台阶,实际上根据例子我们可以发现,是最后一个台阶还要再上一个台阶才是顶部的位置。

基于此,我们可以通过递归五部曲来求解本题。

1.确定dp数组以及下标的含义:我们可以构造一个vector型dp数组,其中dp[i]应该定义为到达第i个台阶所花费的最小体力,这样我们最后求出的dp[cost.size()]才是到达顶部的花费最小体力。

2.确定递推公式:对于第i个台阶来说,有两个途径能够得到dp[i],一个是dp[i - 1],一个是dp[i - 2]而我们需要得到最小的,因此dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])。

3.初始化dp数组:通过递推公式我们知道,至少需要两个数才能够推出后面的值,因此我们可以初始化dp[0] 和 dp[1](注意本题中题干给出了0下标的含义)

4.确定遍历顺序:显然本题也是从前往后进行遍历。

5.举例推导dp数组:

代码:

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        //动态规划
        //1.确定dp数组及下标含义
        vector<int> dp(cost.size() + 1); //dp[n]表示上到第n个台阶所要消耗的最小花费
        //2.确定递推公式 dp[n] = min(dp[n - 1] + cost[n - 1], dp[n - 2] + cost[n - 2]);
        //3.dp数组初始化(规定cost.size() >= 2)
        dp[0] = 0; //爬的时候才消耗费用
        dp[1] = 0;
        //4.确定遍历顺序
        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()];
    }
};

总结 

动态规划开始,牢记动态五部曲,做题不慌张。